斐波那契堆¶

概述¶

斐波那契堆是一种支持高效合并的堆结构，大部分操作达到O(1)摊还时间复杂度。

斐波那契堆特点¶

松散结构：树的组织较为松散
延迟合并：合并操作延迟到删除时
高效插入：O(1)摊还时间
标记机制：记录节点是否失去孩子

数据结构¶

C
typedef struct FibonacciNode {
    int key;
    int degree;
    int marked;
    struct FibonacciNode *parent;
    struct FibonacciNode *child;
    struct FibonacciNode *left;
    struct FibonacciNode *right;
} FibonacciNode;

typedef struct {
    FibonacciNode *min;
    int n;
} FibonacciHeap;

创建节点和堆¶

C
FibonacciNode* createFibonacciNode(int key) {
    FibonacciNode *node = (FibonacciNode*)malloc(sizeof(FibonacciNode));
    node->key = key;
    node->degree = 0;
    node->marked = 0;
    node->parent = NULL;
    node->child = NULL;
    node->left = node;
    node->right = node;
    return node;
}

FibonacciHeap* createFibonacciHeap() {
    FibonacciHeap *heap = (FibonacciHeap*)malloc(sizeof(FibonacciHeap));
    heap->min = NULL;
    heap->n = 0;
    return heap;
}

插入操作¶

C
void insertFibonacci(FibonacciHeap *heap, int key) {
    FibonacciNode *node = createFibonacciNode(key);
    
    if (heap->min == NULL) {
        heap->min = node;
    } else {
        node->left = heap->min;
        node->right = heap->min->right;
        heap->min->right->left = node;
        heap->min->right = node;
        
        if (node->key < heap->min->key) {
            heap->min = node;
        }
    }
    
    heap->n++;
}

合并操作¶

C
FibonacciHeap* unionFibonacci(FibonacciHeap *h1, FibonacciHeap *h2) {
    FibonacciHeap *heap = createFibonacciHeap();
    
    if (h1->min == NULL) {
        heap->min = h2->min;
    } else if (h2->min == NULL) {
        heap->min = h1->min;
    } else {
        FibonacciNode *temp = h1->min->right;
        h1->min->right = h2->min->right;
        h2->min->right->left = h1->min;
        h2->min->right = temp;
        temp->left = h2->min;
        
        heap->min = (h1->min->key < h2->min->key) ? h1->min : h2->min;
    }
    
    heap->n = h1->n + h2->n;
    
    free(h1);
    free(h2);
    
    return heap;
}

提取最小值¶

C
void addToRootList(FibonacciHeap *heap, FibonacciNode *node) {
    if (heap->min == NULL) {
        heap->min = node;
    } else {
        node->left = heap->min;
        node->right = heap->min->right;
        heap->min->right->left = node;
        heap->min->right = node;
    }
}

void removeNode(FibonacciNode *node) {
    node->left->right = node->right;
    node->right->left = node->left;
}

void linkFibonacci(FibonacciNode *y, FibonacciNode *x) {
    removeNode(y);
    
    if (x->child == NULL) {
        x->child = y;
        y->left = y;
        y->right = y;
    } else {
        y->left = x->child;
        y->right = x->child->right;
        x->child->right->left = y;
        x->child->right = y;
    }
    
    y->parent = x;
    x->degree++;
    y->marked = 0;
}

void consolidate(FibonacciHeap *heap) {
    int maxDegree = (int)(log(heap->n) / log(2)) + 1;
    FibonacciNode **degreeArray = (FibonacciNode**)calloc(maxDegree + 1, sizeof(FibonacciNode*));
    
    int rootCount = 0;
    FibonacciNode *curr = heap->min;
    if (curr) {
        rootCount = 1;
        while (curr->right != heap->min) {
            rootCount++;
            curr = curr->right;
        }
    }
    
    FibonacciNode **roots = (FibonacciNode**)malloc(sizeof(FibonacciNode*) * rootCount);
    curr = heap->min;
    for (int i = 0; i < rootCount; i++) {
        roots[i] = curr;
        curr = curr->right;
    }
    
    for (int i = 0; i < rootCount; i++) {
        FibonacciNode *x = roots[i];
        int d = x->degree;
        
        while (degreeArray[d] != NULL) {
            FibonacciNode *y = degreeArray[d];
            
            if (x->key > y->key) {
                FibonacciNode *temp = x;
                x = y;
                y = temp;
            }
            
            linkFibonacci(y, x);
            degreeArray[d] = NULL;
            d++;
        }
        
        degreeArray[d] = x;
    }
    
    heap->min = NULL;
    for (int i = 0; i <= maxDegree; i++) {
        if (degreeArray[i] != NULL) {
            addToRootList(heap, degreeArray[i]);
            
            if (heap->min == NULL || degreeArray[i]->key < heap->min->key) {
                heap->min = degreeArray[i];
            }
        }
    }
    
    free(degreeArray);
    free(roots);
}

int extractMinFibonacci(FibonacciHeap *heap) {
    FibonacciNode *z = heap->min;
    
    if (z != NULL) {
        FibonacciNode *child = z->child;
        if (child != NULL) {
            int childCount = 0;
            FibonacciNode *temp = child;
            do {
                childCount++;
                temp = temp->right;
            } while (temp != child);
            
            FibonacciNode **children = (FibonacciNode**)malloc(sizeof(FibonacciNode*) * childCount);
            temp = child;
            for (int i = 0; i < childCount; i++) {
                children[i] = temp;
                temp = temp->right;
            }
            
            for (int i = 0; i < childCount; i++) {
                addToRootList(heap, children[i]);
                children[i]->parent = NULL;
            }
            
            free(children);
        }
        
        removeNode(z);
        
        if (z == z->right) {
            heap->min = NULL;
        } else {
            heap->min = z->right;
            consolidate(heap);
        }
        
        heap->n--;
    }
    
    int minKey = z ? z->key : -1;
    if (z) free(z);
    return minKey;
}

时间复杂度¶

操作	时间复杂度
插入	O(1) 摊还
合并	O(1)
获取最小值	O(1)
删除最小值	O(log n) 摊还
减少键值	O(1) 摊还
删除	O(log n) 摊还

应用场景¶

Dijkstra算法：优化到O(V log V + E)
Prim算法：优化到O(E + V log V)
大规模图算法：边数远大于顶点数时优势明显

参考资料¶

《算法导论》第19章
Fredman, Tarjan (1987) 原始论文