C++中的Fibonacci Heap（斐波那契堆）：实现高效的优先队列操作与摊还分析

大家好，今天我们来深入探讨一种高级数据结构：Fibonacci Heap（斐波那契堆）。它是一种非常强大的优先队列实现，尤其在需要频繁进行 decrease-key 操作的算法中表现出色，例如 Dijkstra 最短路径算法和 Prim 最小生成树算法。我们将从基本概念入手，逐步讲解其结构、操作、C++代码实现，以及摊还分析。

1. 什么是 Fibonacci Heap？

Fibonacci Heap 是一种支持高效优先队列操作的数据结构，它是一种森林结构，由一组满足最小堆性质的树组成。与二叉堆或二项堆不同，Fibonacci Heap 允许更自由的结构，这使得某些操作（如合并）能够以非常高效的方式完成。

关键特性：

森林结构： Fibonacci Heap 并不是一棵树，而是一组树的集合，每棵树都满足最小堆性质（父节点的键值小于或等于子节点的键值）。
延迟操作： 许多操作（如删除操作）会被延迟执行，这有助于在后续操作中一次性清理堆的结构，从而实现摊还时间复杂度上的优化。
势能函数： 摊还分析的关键在于势能函数，它用于跟踪数据结构的 "潜在能量"，并将其用于平摊操作的实际成本。

2. Fibonacci Heap 的结构

Fibonacci Heap 的基本结构由以下几个部分组成：

节点 (Node): 每个节点包含以下信息：
- key: 节点的键值，用于确定优先级。
- data: 节点存储的数据。
- parent: 指向父节点的指针。
- child: 指向一个子节点的指针。
- left: 指向左兄弟节点的指针。
- right: 指向右兄弟节点的指针。
- mark: 布尔值，用于标记节点是否失去了孩子。
- degree: 节点拥有的孩子数量。
最小指针 (min): 指向整个堆中具有最小键值的节点。这是快速访问最小元素的关键。
节点数量 (n): 堆中节点的总数。

节点结构体的 C++ 代码：

template <typename KeyType, typename DataType>
struct FibonacciHeapNode {
    KeyType key;
    DataType data;
    FibonacciHeapNode* parent;
    FibonacciHeapNode* child;
    FibonacciHeapNode* left;
    FibonacciHeapNode* right;
    bool mark;
    int degree;

    FibonacciHeapNode(KeyType k, DataType d) : key(k), data(d), parent(nullptr), child(nullptr), left(nullptr), right(nullptr), mark(false), degree(0) {}
};

Fibonacci Heap 类：

template <typename KeyType, typename DataType>
class FibonacciHeap {
public:
    FibonacciHeap() : min(nullptr), n(0) {}
    ~FibonacciHeap(); // Destructor to free memory

    FibonacciHeapNode<KeyType, DataType>* insert(KeyType key, DataType data);
    FibonacciHeapNode<KeyType, DataType>* minimum();
    FibonacciHeapNode<KeyType, DataType>* extractMin();
    void unionHeaps(FibonacciHeap& other);
    void decreaseKey(FibonacciHeapNode<KeyType, DataType>* node, KeyType newKey);
    void deleteNode(FibonacciHeapNode<KeyType, DataType>* node);

private:
    FibonacciHeapNode<KeyType, DataType>* min;
    int n;

    void consolidate();
    void cut(FibonacciHeapNode<KeyType, DataType>* node, FibonacciHeapNode<KeyType, DataType>* parent);
    void cascadingCut(FibonacciHeapNode<KeyType, DataType>* node);
    void removeNodeFromList(FibonacciHeapNode<KeyType, DataType>* node); // Helper function
    void addChild(FibonacciHeapNode<KeyType, DataType>* parent, FibonacciHeapNode<KeyType, DataType>* child); // Helper function
};

3. Fibonacci Heap 的操作

接下来，我们详细介绍 Fibonacci Heap 的关键操作，并提供相应的 C++ 代码实现。

3.1. Insert (插入)

插入操作非常简单，创建一个包含给定键值的新节点，并将其添加到根列表中。如果新节点的键值小于当前的 min 指针指向的节点的键值，则更新 min 指针。

C++ 代码：

template <typename KeyType, typename DataType>
FibonacciHeapNode<KeyType, DataType>* FibonacciHeap<KeyType, DataType>::insert(KeyType key, DataType data) {
    FibonacciHeapNode<KeyType, DataType>* newNode = new FibonacciHeapNode<KeyType, DataType>(key, data);
    newNode->left = newNode;
    newNode->right = newNode;

    if (min == nullptr) {
        min = newNode;
    } else {
        // Add newNode to the root list
        newNode->right = min->right;
        newNode->left = min;
        min->right->left = newNode;
        min->right = newNode;

        if (newNode->key < min->key) {
            min = newNode;
        }
    }
    n++;
    return newNode;
}

时间复杂度： O(1)

3.2. Minimum (查找最小值)

minimum 操作直接返回 min 指针指向的节点。

C++ 代码：

template <typename KeyType, typename DataType>
FibonacciHeapNode<KeyType, DataType>* FibonacciHeap<KeyType, DataType>::minimum() {
    return min;
}

时间复杂度： O(1)

3.3. Extract-Min (提取最小值)

extractMin 操作是 Fibonacci Heap 中最复杂的操作之一。它涉及以下步骤：

找到最小节点 (min)。
将 min 节点的所有子节点添加到根列表中。
从根列表中删除 min 节点。
如果 min 节点是堆中唯一的节点，则将 min 设置为 nullptr，否则，将 min 设置为根列表中的任意节点，并调用 consolidate 操作来合并具有相同度数的树。
减少堆中的节点数量 (n)。
返回最小节点。

C++ 代码：

template <typename KeyType, typename DataType>
FibonacciHeapNode<KeyType, DataType>* FibonacciHeap<KeyType, DataType>::extractMin() {
    FibonacciHeapNode<KeyType, DataType>* z = min;

    if (z != nullptr) {
        // Add z's children to the root list
        FibonacciHeapNode<KeyType, DataType>* child = z->child;
        FibonacciHeapNode<KeyType, DataType>* nextChild;
        if (child != nullptr) {
            FibonacciHeapNode<KeyType, DataType>* currentChild = child;
            do {
                nextChild = currentChild->right;
                removeNodeFromList(currentChild);
                currentChild->left = currentChild;
                currentChild->right = currentChild;
                currentChild->parent = nullptr;

                // Add to root list
                currentChild->right = min->right;
                currentChild->left = min;
                min->right->left = currentChild;
                min->right = currentChild;

                currentChild = nextChild;
            } while (currentChild != child);
        }

        // Remove z from the root list
        removeNodeFromList(z);
        if (z == z->right) {
            min = nullptr;
        } else {
            min = z->right;
            consolidate();
        }
        n--;
        return z;
    }
    return nullptr;
}

3.4. Consolidate (合并)

consolidate 操作是 extractMin 操作的关键部分。它的目的是合并具有相同度数的树，以减少根列表中的树的数量。该操作使用一个辅助数组 A，其中 A[i] 存储度数为 i 的树的根节点。

算法步骤：

创建辅助数组 A，大小为 log(n) (实际实现中可能需要动态调整大小).
遍历根列表中的每个节点 x。
令 d 为 x 的度数。
当 A[d] 不为空时，表示存在另一个度数为 d 的节点 y。
比较 x 和 y 的键值，将键值较大的节点作为键值较小节点的子节点。
更新 x 的度数，并将 A[d] 设置为空。
重复步骤 4-6，直到 A[d] 为空。
将 x 存储到 A[d] 中。
遍历辅助数组 A，更新 min 指针。

C++ 代码：

template <typename KeyType, typename DataType>
void FibonacciHeap<KeyType, DataType>::consolidate() {
    int D = static_cast<int>(std::floor(std::log2(n))) + 1; // Maximum degree
    std::vector<FibonacciHeapNode<KeyType, DataType>*> A(D, nullptr);

    // Iterate through the root list
    FibonacciHeapNode<KeyType, DataType>* start = min;
    FibonacciHeapNode<KeyType, DataType>* w = min;
    FibonacciHeapNode<KeyType, DataType>* nextW;

    do {
        nextW = w->right;
        int d = w->degree;

        while (A[d] != nullptr) {
            FibonacciHeapNode<KeyType, DataType>* y = A[d];
            if (w->key > y->key) {
                std::swap(w, y);
            }
            // Make y a child of w
            addChild(w, y);
            A[d] = nullptr;
            d++;
        }
        A[d] = w;
        w = nextW;
    } while (w != start);

    // Rebuild the root list from A and find the new minimum
    min = nullptr;
    for (int i = 0; i < D; ++i) {
        if (A[i] != nullptr) {
            if (min == nullptr) {
                min = A[i];
                min->left = min;
                min->right = min;
            } else {
                // Add A[i] to the root list
                A[i]->right = min->right;
                A[i]->left = min;
                min->right->left = A[i];
                min->right = A[i];

                if (A[i]->key < min->key) {
                    min = A[i];
                }
            }
        }
    }
}

template <typename KeyType, typename DataType>
void FibonacciHeap<KeyType, DataType>::addChild(FibonacciHeapNode<KeyType, DataType>* parent, FibonacciHeapNode<KeyType, DataType>* child) {
    // Remove child from its current list
    removeNodeFromList(child);

    child->parent = parent;
    if (parent->child == nullptr) {
        parent->child = child;
        child->left = child;
        child->right = child;
    } else {
        // Add child to the child list of parent
        child->right = parent->child;
        child->left = parent->child->left;
        parent->child->left->right = child;
        parent->child->left = child;
    }
    parent->degree++;
    child->mark = false;  // Reset mark on the new child
}

时间复杂度： O(log n) 摊还时间

3.5. Decrease-Key (减小键值)

decreaseKey 操作允许减小堆中一个节点的键值。如果减小后的键值小于其父节点的键值，则需要将该节点从其父节点处切断，并将其添加到根列表中。为了防止过度切割，每个节点都有一个 mark 标记。如果一个节点失去了它的第一个孩子，则将其标记为 true。如果它失去了第二个孩子，则将其从其父节点处切断，并递归地对它的祖先执行此操作（cascadingCut）。

C++ 代码：

template <typename KeyType, typename DataType>
void FibonacciHeap<KeyType, DataType>::decreaseKey(FibonacciHeapNode<KeyType, DataType>* node, KeyType newKey) {
    if (newKey > node->key) {
        // Error: New key is greater than current key
        return;
    }

    node->key = newKey;
    FibonacciHeapNode<KeyType, DataType>* parent = node->parent;

    if (parent != nullptr && node->key < parent->key) {
        cut(node, parent);
        cascadingCut(parent);
    }

    if (node->key < min->key) {
        min = node;
    }
}

3.6. Cut (切割)

cut 函数将一个节点从其父节点处切断，并将其添加到根列表中。

C++ 代码：

template <typename KeyType, typename DataType>
void FibonacciHeap<KeyType, DataType>::cut(FibonacciHeapNode<KeyType, DataType>* node, FibonacciHeapNode<KeyType, DataType>* parent) {
    // Remove node from parent's child list
    removeNodeFromList(node);
    parent->degree--;

    if (parent->child == node) {
        if (node->right == node) {
            parent->child = nullptr;
        } else {
            parent->child = node->right;
        }
    }

    // Add node to the root list
    node->right = min->right;
    node->left = min;
    min->right->left = node;
    min->right = node;
    node->parent = nullptr;
    node->mark = false;
}

3.7. Cascading-Cut (级联切割)

cascadingCut 函数递归地对节点的祖先执行切割操作，直到遇到根节点或未标记的节点。

C++ 代码：

template <typename KeyType, typename DataType>
void FibonacciHeap<KeyType, DataType>::cascadingCut(FibonacciHeapNode<KeyType, DataType>* node) {
    FibonacciHeapNode<KeyType, DataType>* parent = node->parent;
    if (parent != nullptr) {
        if (!node->mark) {
            node->mark = true;
        } else {
            cut(node, parent);
            cascadingCut(parent);
        }
    }
}

3.8. Delete (删除)

deleteNode 操作首先将要删除的节点的键值减小到负无穷，然后调用 extractMin 操作来将其从堆中删除。

C++ 代码：

template <typename KeyType, typename DataType>
void FibonacciHeap<KeyType, DataType>::deleteNode(FibonacciHeapNode<KeyType, DataType>* node) {
    // Assuming KeyType can represent negative infinity (e.g., numeric types)
    KeyType negativeInfinity = std::numeric_limits<KeyType>::lowest();
    decreaseKey(node, negativeInfinity);
    extractMin();
}

3.9. Union (合并)

unionHeaps 操作将两个 Fibonacci Heap 合并成一个。它简单地将两个根列表连接起来，并更新 min 指针。

C++ 代码：

template <typename KeyType, typename DataType>
void FibonacciHeap<KeyType, DataType>::unionHeaps(FibonacciHeap& other) {
    if (min == nullptr) {
        min = other.min;
    } else if (other.min != nullptr) {
        // Concatenate the root lists
        FibonacciHeapNode<KeyType, DataType>* minRight = min->right;
        FibonacciHeapNode<KeyType, DataType>* otherMinLeft = other.min->left;

        min->right = other.min;
        other.min->left = min;
        minRight->left = otherMinLeft;
        otherMinLeft->right = minRight;

        if (other.min->key < min->key) {
            min = other.min;
        }
    }

    n += other.n;

    // Clear the other heap (important to prevent double freeing)
    other.min = nullptr;
    other.n = 0;
}

3.10. Helper Function: removeNodeFromList

这是一个辅助函数，用于从双向链表中移除一个节点。

C++ 代码:

template <typename KeyType, typename DataType>
void FibonacciHeap<KeyType, DataType>::removeNodeFromList(FibonacciHeapNode<KeyType, DataType>* node) {
    FibonacciHeapNode<KeyType, DataType>* left = node->left;
    FibonacciHeapNode<KeyType, DataType>* right = node->right;
    left->right = right;
    right->left = left;
}

3.11. Destructor

template <typename KeyType, typename DataType>
FibonacciHeap<KeyType, DataType>::~FibonacciHeap() {
    if (min == nullptr) return;

    FibonacciHeapNode<KeyType, DataType>* current = min;
    FibonacciHeapNode<KeyType, DataType>* next;

    do {
        next = current->right;

        // Recursively delete children
        if (current->child != nullptr) {
            FibonacciHeap childHeap;
            childHeap.min = current->child;
            FibonacciHeapNode<KeyType, DataType>* lastChild = current->child->left;

            // Detach children from the current node
            current->child->left = current->child;
            current->child->right = current->child;
            current->child = nullptr;

            childHeap.n = current->degree;
            current->degree = 0;

            childHeap.~FibonacciHeap(); // Recursively delete the child heap
        }
        delete current; // Delete the current node
        current = next;
    } while (current != min);

    min = nullptr;
    n = 0;
}

4. Fibonacci Heap 的摊还分析

Fibonacci Heap 的高效性源于其摊还分析。摊还分析是一种用于分析算法时间复杂度的技术，它关注一系列操作的平均成本，而不是单个操作的最坏情况成本。

势能函数：

Fibonacci Heap 的摊还分析使用以下势能函数：

Φ(H) = t(H) + 2m(H)

其中：

t(H) 是 Fibonacci Heap H 中根列表中的树的数量。
m(H) 是 H 中被标记的节点的数量。

摊还成本：

一个操作的摊还成本定义为：

c_i' = c_i + Φ(H_i) - Φ(H_{i-1})

其中：

c_i' 是第 i 个操作的摊还成本。
c_i 是第 i 个操作的实际成本。
Φ(H_i) 是第 i 个操作后的势能。
Φ(H_{i-1}) 是第 i-1 个操作后的势能。

摊还时间复杂度：

以下是 Fibonacci Heap 的操作的摊还时间复杂度：

操作	实际成本	势能变化	摊还成本
Insert	O(1)	O(1)	O(1)
Minimum	O(1)	O(0)	O(1)
Extract-Min	O(log n)	O(log n)	O(log n)
Union	O(1)	O(0)	O(1)
Decrease-Key	O(1)	O(1)	O(1)
Delete	O(log n)	O(log n)	O(log n)

解释：

Insert: 实际成本是 O(1)，势能增加 1（因为根列表中的树的数量增加 1），因此摊还成本是 O(1)。
Extract-Min: 实际成本是 O(log n)（由于 consolidate 操作），势能变化也是 O(log n)（由于树的合并和标记的调整），因此摊还成本是 O(log n)。
Decrease-Key: 实际成本是 O(1)，势能可能增加（由于标记）或减少（由于切割），但摊还成本仍然是 O(1)。

5. 总结表格

操作	摊还时间复杂度
Insert	O(1)
Minimum	O(1)
Extract-Min	O(log n)
Union	O(1)
Decrease-Key	O(1)
Delete	O(log n)

6. Fibonacci Heap 的优势与劣势

优势：

高效的 decreaseKey 操作： 这是 Fibonacci Heap 的主要优势，使其在需要频繁进行键值减小操作的算法中非常有用。
摊还时间复杂度： 虽然某些单个操作可能需要较长的时间，但一系列操作的平均成本非常低。

劣势：

复杂的实现： Fibonacci Heap 的实现比二叉堆或二项堆复杂得多。
常数因子： 虽然摊还时间复杂度较低，但常数因子可能较高，这意味着对于较小的数据集，它可能不如其他优先队列实现快。
内存开销： 每个节点都需要额外的指针和标记，这会增加内存开销。

7. 使用场景

Fibonacci Heap 最适合以下场景：

Dijkstra 最短路径算法： 用于实现高效的最短路径查找。
Prim 最小生成树算法： 用于构建最小生成树。
需要频繁进行 decreaseKey 操作的算法。

8. 代码优化的建议

内存管理： 使用自定义内存分配器可以提高性能，尤其是在需要频繁创建和删除节点的情况下。
循环展开： 在 consolidate 操作中，可以使用循环展开来减少循环开销。
编译器优化： 使用编译器优化选项（如 -O3）可以提高代码的执行速度。

9. 实现要点

双向链表操作: 掌握双向链表的插入和删除操作是实现 Fibonacci Heap 的基础。
consolidate 操作的实现: consolidate 操作是 Fibonacci Heap 实现中最复杂的部分，需要仔细设计和测试。
势能函数的理解: 理解势能函数是进行摊还分析的关键。
正确处理边界情况: 确保代码能够正确处理空堆、单节点堆等边界情况。

10. 总结：高效的优先队列，但实现复杂

Fibonacci Heap 是一种强大的优先队列实现，特别适用于需要频繁执行 decrease-key 操作的算法。虽然其实现相对复杂，且常数因子较高，但在特定场景下，它能提供卓越的性能。理解其结构、操作和摊还分析是掌握这种数据结构的关键。

更多IT精英技术系列讲座，到智猿学院