《算法导论》第19章-斐波那契堆 引入&& 19.1 斐波那契堆结构

引入

1、可合并堆
可合并堆(mergeable heap)是支持以下5种操作：
MAKE-HEAP():创建和返回一个新的不含任何元素的堆。
INSERT(H，x):将一个已填人关键字的元素x插人堆H中。
MINIMUM(H):返回一个指向堆H中具有最小关键字元素的指针。
EXTRACT-MIN(H):从堆H中删除最小关键字的元素，并返回一个指向该元素的指针。
UNION(H,H2):创建并返回-一个包含堆H和堆H2中所有元素的新堆。堆H和堆H2由这一操作“销毁”。
除了以上可合并堆的操作外，斐波那契堆还支持以下两种操作:
DECREASE-KEY(H, x, k):将堆H中元素x的关键字赋予新值k。假定新值k不大于当前的关键字。
DELETE(H, x):从堆H中删除元素x。

19.1 斐波那契堆结构

1、一个斐波那契堆是一系列具有最小堆序(min heap ordered) 的有根树的集合。也就是说，每棵树均遵循最小堆性质( min-heap property):每个结点的关键字大于或等于它的父结点的关键字。图19-2(a)是一个斐波那契堆的例子。

2、如图19-2(b)所示，每个结点x包含一个指向它父结点的指针x. p和一个指向它的一个孩子的指针x. child.。x的所有孩子被链接成一个环形的双向链表，称为x的孩子链表(child list)。孩子链表中的每个孩子y均有指针y. left和y. right,分别指向y的左兄弟和右兄弟。如果y是仅有的一个孩子，则y. left=y. right=y。孩子链表中各兄弟出现的次序是任意的。
3、每个结点有另外两个属性。把结点x的孩子链表中的孩子数目储存在x. degree。布尔值属性x. mark指示结点x自从上一次成为另一个结点的孩子后，是否失去过孩子。新产生的结点是未被标记的，并且当结点x成为另一个结点的孩子时，它便成为未被标记结点。
直到19.3节的DECREASE-KEY操作，我们才把所有的mark属性值设为FALSE。
4、通过指针H.min来访问一个给定的斐波那契堆H,该指针指向具有最小关键字的树的根结点，我们把这个结点称为斐波那契堆的最小结点(minimum node)。如果不止一个根结点具有最小关键字，那么这些根结点中的任何-一个都有可能成为最小结点。如果一个斐波那契堆H是空的，那么H.min为NIL。在斐波那契堆中，所有树的根都用其left和right指针链成一个环形的双链表，该双链表称为斐波那契堆的根链表(root list)。因此，指针H. min指向根链表中关键字最小的那个结点。根链表中的树次序可以任意。