fibonacci堆的一种实现
fibheap的Python项目详细描述
斐波那契堆
斐波纳契堆概述
描述了数据结构及其操作。（第19章）fibonacci堆支持可合并堆操作，包括make heap、insert、minimum、extract min和union。数据结构还支持键减少和删除，尽管使用这两个操作需要用户为项本身创建节点。
表示法
节点
每个节点都具有以下属性：
- 左，右：节点的相邻兄弟节点。节点及其同级节点是双重链接的，因此它们形成一个循环。如果x是独生子，它就是自己的左右兄弟。
- child：节点的代表子节点。要访问节点的所有子节点，请首先访问代表子节点，然后通过左右属性访问代表子节点的所有同级节点
- 家长
- degree：节点的子节点数
- mark:（cormen等人的描述）为true或false，表示该节点自上次成为另一个节点的子节点以来是否丢失了子节点。新创建的节点未标记。当一个节点成为另一个节点的子节点时，它将变为未标记。
斐波纳契堆
堆具有以下属性：
- min：指向包含最小键的节点
- 堆中当前的节点数
- 树上的根数。fibonacci堆可以包含许多最小有序堆树。这些树的根是双重连接的，形成一个循环，就像兄弟姐妹一样。fibonacci堆的树数总是根数。
- 堆中标记的节点数
操作概述
使堆
在最坏情况下运行。初始化空堆。
插入
在最坏情况下运行。将节点添加为堆的根。
最小值
在最坏情况下运行。返回堆的min属性。
提取最小值
在摊销时间内运行。移除并返回最小节点。此过程将最小节点的每个子节点移动到根列表，从根列表中删除最小节点本身，并合并生成的树以减少树的数量。
联合体
在最坏情况下运行。生成并返回两个堆的并集。这个过程只是连接两个根列表。
减小键
在摊销时间内运行。将节点x的键减小到k。
删除
在摊销时间内运行。首先将x的键设置为负无穷大并提取堆的最小值，从而从堆中删除x。
使用
使用PIP安装：
>>> pip install fibheap
使用可分堆操作：
>>> from fibheap import * >>> heap1= makefheap()>>> heap2= makefheap()>>> num_list1=[1,4,2]>>> num_list2=[6,-1,0]>>> for num in num_list1: ... fheappush(heap1, num)... >>> for num in num_list2: ... fheappush(heap2, num)... >>> fheapunion(heap1, heap2)>>> getfheapmin(heap1)-1>>> sorted_list=[]>>> while heap1.num_nodes: ... sorted_list.append(fheappop(heap1))... >>> sorted_list [-1, 0, 1, 2, 4, 6]
当数据包含多个数字时：
>>> item_list=[(3, 'a'),(0, 'z'), (2,'m'), (-2, 'r')]>>> heap= makefheap()>>> for item in item_list: ... fheappush(heap, item)... >>> sorted_list=[]>>> while heap.num_nodes: ... sorted_list.append(fheappop(heap))... >>> sorted_list [(-2, 'r'), (0, 'z'), (2, 'm'), (3, 'a')]
欢迎加入QQ群-->： 979659372
