您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> C++ 入門

斐波那契堆 C++ 完整實現詳解（下）：核心操作與代碼深度解析

編輯：C++ 入門

回顧與導讀

上一篇介紹了斐波那契堆的節點結構、類定義與基本屬性。本文將深入講解插入、合併、刪除最小節點、鏈接、鍵值更新、刪除節點等核心操作的算法邏輯與 C++ 實現細節。

1. 插入操作 —— O(1) 平攤

思路：新節點單獨構成一棵樹，直接插入根鏈表的 min 節點之前（雙向循環鏈表尾部）。若新節點鍵值更小，更新 min 指針。

template <class T>
void FibHeap<T>::addNode(FibNode<T>* node, FibNode<T>* root) {
    node->left = root->left;
    root->left->right = node;
    node->right = root;
    root->left = node;
}

template <class T>
void FibHeap<T>::insert(FibNode<T>* node) {
    if (keyNum == 0) min = node;
    else {
        addNode(node, min);
        if (node->key < min->key) min = node;
    }
    ++keyNum;
}

關鍵點：根鏈表是雙向循環鏈表，min 作為「頭結點」，插入到 min 之前相當於插到表尾，O(1) 指針操作。

2. 合併操作 —— O(1) 平攤

思路：將兩堆的根鏈表拼接成一個雙向循環鏈表，比較兩堆 min 更新全局最小，釋放被合併堆的輔助內存 cons。

template <class T>
void FibHeap<T>::catList(FibNode<T>* a, FibNode<T>* b) {
    FibNode<T>* tmp = a->right;
    a->right = b->right;
    b->right->left = a;
    b->right = tmp;
    tmp->left = b;
}

template <class T>
void FibHeap<T>::combine(FibHeap<T>* other) {
    if (!other) return;
    if (other->maxDegree > maxDegree) swap(*this, *other); // 保證 this 容量較大

    if (!min) { min = other->min; keyNum = other->keyNum; }
    else if (other->min) {
        catList(min, other->min);
        if (other->min->key < min->key) min = other->min;
        keyNum += other->keyNum;
    }
    free(other->cons);
    delete other;
}

3. 刪除最小節點 —— O(log n) 平攤

最複雜的操作，分三步：

移除 min：將其子鏈表併入根鏈表
Consolidate（合併同度樹）：掃描根鏈表，用 cons[degree] 數組記錄每度數的樹，相同度數則 link 合併，直到每度數最多一棵樹
重新掃描根鏈表找新 min

template <class T>
FibNode<T>* FibHeap<T>::extractMin() {
    FibNode<T>* z = min;
    if (z) {
        // 1. 子節點提升為根
        if (z->child) {
            FibNode<T>* child = z->child;
            do {
                FibNode<T>* next = child->right;
                addNode(child, min); // 插入根鏈表
                child->parent = nullptr;
                child = next;
            } while (child != z->child);
        }
        // 2. 從根鏈表移除 z
        removeNode(z);
        if (z == z->right) min = nullptr; // 只剩 z 一個節點
        else {
            min = z->right;
            consolidate(); // 核心合併
        }
        --keyNum;
    }
    return z;
}

template <class T>
void FibHeap<T>::consolidate() {
    makeCons(); // 確保 cons 數組足夠大
    // 初始化 cons 為 nullptr
    for (int i = 0; i <= maxDegree; ++i) cons[i] = nullptr;

    // 遍歷根鏈表
    int numRoots = 0;
    FibNode<T>* x = min;
    do { ++numRoots; x = x->right; } while (x != min);

    while (numRoots--) {
        FibNode<T>* curr = x;
        x = x->right;
        int d = curr->degree;
        while (cons[d]) {
            FibNode<T>* y = cons[d];
            if (curr->key > y->key) swap(curr, y); // 保證 curr 為較小者
            link(y, curr); // y 成為 curr 的子
            cons[d] = nullptr;
            ++d;
        }
        cons[d] = curr;
    }
    // 重建根鏈表並找新 min
    min = nullptr;
    for (int i = 0; i <= maxDegree; ++i) {
        if (cons[i]) {
            if (!min) {
                min = cons[i];
                min->left = min->right = min;
            } else {
                addNode(cons[i], min);
                if (cons[i]->key < min->key) min = cons[i];
            }
        }
    }
}

4. 鍵值減小 —— O(1) 平攤

僅允許減小鍵值（最小堆性質）。若減小後小於父節點，觸發 Cut（剪切） 並可能引發 Cascading Cut（級聯剪切）。

template <class T>
void FibHeap<T>::decrease(FibNode<T>* node, T key) {
    if (key > node->key) return; // 不允許增大
    node->key = key;
    FibNode<T>* parent = node->parent;
    if (parent && node->key < parent->key) {
        cut(node, parent);
        cascadingCut(parent);
    }
    if (node->key < min->key) min = node;
}

template <class T>
void FibHeap<T>::cut(FibNode<T>* node, FibNode<T>* parent) {
    // 從父節點子鏈表移除
    removeNode(node);
    --parent->degree;
    // 加入根鏈表
    addNode(node, min);
    node->parent = nullptr;
    node->marked = false;
}

template <class T>
void FibHeap<T>::cascadingCut(FibNode<T>* node) {
    FibNode<T>* parent = node->parent;
    if (parent) {
        if (!node->marked) node->marked = true; // 首次失去子，標記
        else {
            cut(node, parent); // 二次失去子，剪切上移
            cascadingCut(parent); // 遞歸向上
        }
    }
}

marked 標記意義：記錄節點是否已失去過一個孩子。首次失去只標記，二次失去才剪切，這保證了度數下界為 Fibonacci 數列，從而證明 maxDegree = O(log n)。

5. 刪除任意節點 —— O(log n) 平攤

remove(key) = decrease(node, -∞) + extractMin()。
模板類中用 numeric_limits<T>::min() 或自定義極小值實現。

6. 查找節點 —— O(n)

斐波那契堆不支持高效查找，需在根鏈表及各子樹中遞歸 DFS 查找，僅用於演示/調試。

完整測試主程序

int main() {
    FibHeap<int> heap;
    vector<int> vals = {5, 2, 8, 1, 9, 3};
    for (int v : vals) heap.insert(new FibNode<int>(v));

    cout << "Min: " << heap.minimum() << endl; // 1
    heap.removeMin();
    cout << "Min after pop: " << heap.minimum() << endl; // 2

    // 測試 decrease key
    FibNode<int>* node = heap.search(9);
    heap.decrease(node, 0);
    cout << "Min after decrease 9->0: " << heap.minimum() << endl; // 0

    heap.print(); // 結構驗證
    return 0;
}

性能對比與應用場景

典型應用：Dijkstra、Prim 算法中作為優先隊列，大幅降低稠密圖的時間複雜度（O(E + V log V) vs O(E log V)）。

常見坑點提醒

cons 數組大小需動態擴展（maxDegree ≈ log_φ(n)），否則大數據下越界
link 時必須正確維護雙向鏈表指針與 parent、degree
cascadingCut 遞歸深度可能達 O(log n)，極端情況需改寫為迭代防棧溢出
模板類 T 需支持 <、==、賦值、拷貝構造

總結

斐波那契堆通過「延遲合併」與「標記剪切」機制，將 Insert/Merge/DecreaseKey 的平攤複雜度降至 O(1)，是理論計算機科學中最優雅的數據結構之一。雖然常數因子較大、實際工程中較少直接使用（常被配對堆或鬆弛堆替代），但其設計思想——平攤分析、势能函數、延遲操作——是高級算法研究的必修課。