斐波纳契堆

维基百科，自由的百科全书

	本條目正在從其他語言的維基百科內容翻譯成中文。 歡迎您積極參與翻譯與修訂。

費伯納西堆積樹(Fibonacci heap)是计算机科学中最小堆有序树的集合。它和二项式堆有类似的性质，可用于实现可合并优先队列。

目录 1 结构 2 操作 2.1 建立一个新的斐波纳契堆 2.2 插入一个节点 2.3 查找最小的节点 2.4 合并两个斐波纳契堆 2.5 释放最小的节点

[编辑] 结构

費伯納西堆積樹中的树都是有根的但是无序。每个节点x包含指向父节点的指针p[x]和指向任意一个子结点的child[x]。x的所有子节点都用双向循环链表链接起来，叫做x的子链表。子链表中的每一个节点y都有指向它的左兄弟的left[y]和右兄弟的right[y]。如果节点y是x仅有的子节点，则left[y]=right[y]=y。

[编辑] 操作

[编辑] 建立一个新的斐波纳契堆

[编辑] 插入一个节点

[编辑] 查找最小的节点

[编辑] 合并两个斐波纳契堆

[编辑] 释放最小的节点