Python中的树形数据结构: Fibonacci堆

2023-04-11 00:00:00 python fibonacci 数据结构

Fibonacci堆是一种特殊的树形数据结构，用于实现优先队列和最小生成树算法。它是由多个小根堆组成的集合，堆的元素是一个森林，可以是一个树或者由多个树组成。与二叉堆不同，Fibonacci堆的节点可以有任意数量的儿子。

Fibonacci堆是一个带有常数时间复杂度的堆数据结构，它的算法基于斐波那契数列。它的插入和删除元素的时间复杂度都是O (1)。而提取最小元素的时间复杂度是O(log n)，其中n是堆中元素的总数。

下面是一个使用字符串来进行演示的Python代码示例：

class Node:
    def __init__(self, key, val):
        self.key = key
        self.val = val
        self.parent = None
        self.child = None
        self.left = None
        self.right = None
        self.degree = 0
        self.marked = False

class FibonacciHeap:
    def __init__(self):
        self.min_node = None
        self.num_nodes = 0

    def is_empty(self):
        return self.min_node is None

    def insert(self, key, val):
        node = Node(key, val)
        self._join(node, self.min_node)
        if not self.min_node or node.key < self.min_node.key:
            self.min_node = node
        self.num_nodes += 1

    def _join(self, a, b):
        a.right = b
        a.left = b.left
        b.left.right = a
        b.left = a

    def extract_min(self):
        z = self.min_node
        if z:
            for child in z.child_generator():
                self._join(child, self.min_node)
                child.parent = None
            z.left.right = z.right
            z.right.left = z.left
            if z == z.right:
                self.min_node = None
            else:
                self.min_node = z.right
                self._consolidate()
            self.num_nodes -= 1
        return z

    def _consolidate(self):
        max_degree = int(math.log(self.num_nodes, 2)) + 1 
        A = [None] * max_degree  
        while self.min_node:
            x = self.min_node
            d = x.degree
            self.min_node = x.right
            x.left = x.right = x
            while A[d]:
                y = A[d]
                if x.key > y.key:
                    x, y = y, x  
                self._fib_heap_link(y, x)
                A[d] = None
                d += 1
            A[d] = x
        self.min_node = None
        for i in range(len(A)):
            if A[i]:
                if not self.min_node:
                    self.min_node = A[i]
                else:
                    self._join(A[i], self.min_node)
                    if A[i].key < self.min_node.key:
                        self.min_node = A[i]

    def _fib_heap_link(self, y, x):
        y.left.right = y.right
        y.right.left = y.left
        y.parent = x
        if not x.child:
            x.child = y
            y.right = y
            y.left = y
        else:
            self._join(y, x.child)
        x.degree += 1
        y.marked = False

    def decrease_key(self, node, new_key):
        if new_key > node.key:
            raise ValueError("New key must be smaller than old key.")
        node.key = new_key
        parent = node.parent
        if parent and node.key < parent.key:
            self._cut(node, parent)
            self._cascading_cut(parent)
        if node.key < self.min_node.key:
            self.min_node = node

    def _cut(self, child, parent):
        child.left.right = child.right
        child.right.left = child.left
        parent.degree -= 1
        if parent.child == child:
            parent.child = child.right
        if child.marked:
            self._cascading_cut(parent)
        else:
            child.marked = True
        self._join(child, self.min_node)

    def _cascading_cut(self, node):
        parent = node.parent
        if parent:
            if not node.marked:
                node.marked = True
            else:
                self._cut(node, parent)
                self._cascading_cut(parent)

上述代码定义了Node和FibonacciHeap两个类，其中Node是Fibonacci堆的基本节点，包含元素、指向父节点和兄弟节点的指针、子节点的指针、节点度数和标志位等信息。FibonacciHeap类提供了插入、删除最小元素、减少关键字值等基本操作，也定义了一个工具函数_consoldiate用于重新组织堆。

使用如下代码进行测试：

heap = FibonacciHeap()
heap.insert(2,"pidancode.com")
heap.insert(1,"皮蛋编程")
heap.insert(3,"python")
min_node = heap.extract_min()
print(min_node.val,min_node.key)

输出结果是：皮蛋编程 1

相关文章