斐波那契堆

Fibonacci Heap | 斐波那契堆

Overview | 概述

A Fibonacci Heap is an advanced data structure that extends the concept of a binary heap, optimized for better amortized time complexity, especially in graph algorithms like Dijkstra’s shortest path and Prim’s minimum spanning tree. Unlike binary heaps, Fibonacci heaps provide more efficient support for operations like merging and decreasing keys.

斐波那契堆是一种高级数据结构，扩展了二叉堆的概念，优化了 摊还时间 复杂度，尤其在 Dijkstra 最短路径和 Prim 最小生成树等图算法中表现突出。与二叉堆不同，斐波那契堆在合并和减少键值等操作上提供了更高效的支持。

Structure | 结构

• Node | 节点: Each node in a Fibonacci heap contains a key, pointers to its parent, one of its children, and its siblings. Nodes also store their degree (number of children) and a marked status (indicating whether they lost a child since becoming a child of another node). 节点: 斐波那契堆中的每个节点包含一个键值、指向其父节点、子节点和兄弟节点的指针。节点还存储其度（子节点数量）和标记状态（表示自成为另一个节点的子节点后是否失去了一个子节点）。

• Min-Heap Property | 最小堆性质: For any node $\mathbf{x}$, the key of $\mathbf{x}$ is less than or equal to the keys of its children. 最小堆性质: 对于任意节点 $\mathbf{x}$，其键值不大于其子节点的键值。

• Root List | 根列表: A circular doubly linked list that contains the roots of the trees in the heap. The minimum node is explicitly tracked. 根列表: 一个循环双向链表，包含堆中各树的根节点，并显式跟踪最小节点。

• Marked Nodes | 标记节点: A node is marked if it loses a child after becoming a child of another node. Marked nodes are crucial in maintaining the heap’s efficiency. 标记节点: 如果一个节点在成为另一个节点的子节点后失去了一个子节点，它会被标记。标记节点对于维护堆的效率至关重要。

Operations and Time Complexity | 操作与时间复杂度

Insertion | 插入

• Operation | 操作: Add a new node to the root list.
• Amortized Time | 摊销时间: $O(1)$

def insert(heap, node):
    node.degree = 0
    node.parent = None
    node.child = None
    node.marked = False
    heap.root_list.append(node)
    if heap.min is None or node.key < heap.min.key:
        heap.min = node
    heap.n += 1

Find Minimum | 查找最小值

• Operation | 操作: Return the minimum node.
• Time Complexity | 时间复杂度: $O(1)$

def find_min(heap):
    return heap.min

Union (Meld) | 合并

• Operation | 操作: Concatenate the root lists of two heaps and update the minimum node.
• Amortized Time | 摊销时间: $O(1)$

def union(heap1, heap2):
    new_heap = FibonacciHeap()
    new_heap.root_list = heap1.root_list + heap2.root_list
    if heap1.min is None or (heap2.min is not None and heap2.min.key < heap1.min.key):
        new_heap.min = heap2.min
    else:
        new_heap.min = heap1.min
    new_heap.n = heap1.n + heap2.n
    return new_heap

Extract Minimum | 提取最小值

• Operation | 操作: Remove the minimum node, promote its children to the root list, and consolidate the trees.
• Amortized Time | 摊销时间: $O(\log n)$

def extract_min(heap):
    z = heap.min
    if z is not None:
        for child in z.children():
            heap.root_list.append(child)
            child.parent = None
        heap.root_list.remove(z)
        if not heap.root_list:
            heap.min = None
        else:
            heap.min = heap.root_list[0]
            consolidate(heap)
        heap.n -= 1
    return z

Consolidate | 合并

• Operation | 操作: Combine trees of the same degree in the root list until no two trees have the same degree.
• Time Complexity | 时间复杂度: $O(\log n)$

def consolidate(heap):
    A = [None] * heap.n
    for w in heap.root_list:
        x = w
        d = x.degree
        while A[d] is not None:
            y = A[d]
            if x.key > y.key:
                x, y = y, x
            heap.link(y, x)
            A[d] = None
            d += 1
        A[d] = x
    heap.min = None
    for i in range(heap.n):
        if A[i] is not None:
            if heap.min is None or A[i].key < heap.min.key:
                heap.min = A[i]

Decrease Key | 减小键值

• Operation | 操作: Decrease the key of a node, and if the heap property is violated, cut the node and move it to the root list. If its parent is marked, perform a cascading cut.
• Amortized Time | 摊销时间: $O(1)$

def decrease_key(heap, node, new_key):
    if new_key > node.key:
        raise ValueError("New key is greater than current key")
    node.key = new_key
    y = node.parent
    if y is not None and node.key < y.key:
        cut(heap, node, y)
        cascading_cut(heap, y)
    if node.key < heap.min.key:
        heap.min = node

Delete | 删除

• Operation | 操作: Decrease the key to negative infinity, then extract the minimum.
• Amortized Time | 摊销时间: $O(\log n)$

def delete(heap, node):
    decrease_key(heap, node, float('-inf'))
    extract_min(heap)

Cut and Cascading Cut | 剪切与级联剪切

def cut(heap, x, y):
    y.child.remove(x)
    y.degree -= 1
    heap.root_list.append(x)
    x.parent = None
    x.marked = False
 
def cascading_cut(heap, y):
    z = y.parent
    if z is not None:
        if y.marked:
            cut(heap, y, z)
            cascading_cut(heap, z)
        else:
            y.marked = True

Complexity Analysis | 复杂度分析

The Fibonacci Heap provides superior amortized time complexities for several operations compared to binary heaps due to its lazy merging, cascading cuts, and amortized analysis through the potential method.

斐波那契堆通过懒合并、级联剪切和潜能法摊销分析，提供了比二叉堆更好的操作摊销时间复杂度。

Comparison with Binary Heap | 与二叉堆的比较

• Binary Heap | 二叉堆:

  • Insertion: $O(\log n)$
  • Decrease Key: $O(\log n)$
  • Extract Minimum: $O(\log n)$
  • Merge: $O(n)$

• Fibonacci Heap | 斐波那契堆:

  • Insertion: $O(1)$ (amortized)
  • Decrease Key: $O(1)$ (amortized)
  • Extract Minimum: $O(\log n)$ (amortized)
  • Merge: $O(1)$ (amortized)

Why Fibonacci Heap is Faster | 为什么斐波那契堆更快

1. Lazy Merging | 懒合并: Postponing the reorganization of trees allows for efficient merges and reduces immediate costs. 懒合并: 推迟树的重组，允许高效合并并降低即时开销。

2. Cascading Cuts | 级联剪切: By cutting nodes and moving them to the root list when the heap property is violated, the structure remains flatter, which accelerates future operations. 级联剪切: 通过在堆性质被破坏时剪切节点并将其移动到根列表，结构保持更扁平，加快了未来操作的速度。

3. Amortized Analysis | 摊销分析: Although individual operations might be costly, the potential method ensures that the average cost over a sequence of operations remains low. 摊销分析: 尽管某些单个操作可能代价较高，但潜能法确保一系列操作的平均成本保持较低。

This makes Fibonacci Heaps particularly useful in scenarios involving a large number of decrease-key and merge operations, such as in advanced graph algorithms.

这使得斐波那契堆在涉及大量减小键值和合并操作的场景（如高级图算法中）特别有用。