算法导论第19章--斐波那契堆
可合并(最小)堆(mergeable min-heap) : 支持以下5种操作的一种数据结构, 其中每一个元素都有一个关键字:
- MAKE-HEAP(): 创建和返回一个新的不含任何元素的堆.
- INSERT(H, x): 将一个已填入关键字的元素x插入堆H中.
- MINIMUM(H): 返回一个指向堆H中具有最小关键字元素的指针.
- EXTRACT-MIN(H): 从堆H中删除最小关键字的元素, 并返回一个指向该元素的指针.
- UNION(H1, H2): 创建并返回一个包含堆H1和堆H2中所有元素的新堆, 原来的H1和H2被销毁.
斐波那契堆 : 除可合并堆支持的操作外, 还支持以下两种操作:
- DECREASE-KEY(H, x, k): 将堆H中元素x的关键字赋予新值k, 且k不大于当前的关键字.
- DELETE(H, x): 从堆H中删除元素x.
19.1 斐波那契堆结构
斐波那契堆 : 一系列具有最小堆序的有根树的集合, 即每棵树均遵循最小堆性质.
斐波那契堆的结构:
- 每个结点x包含一个指向父结点的指针x.p, 一个指向它的某一个孩子的指针x.child.
- x的所有孩子被链接成一个环形的双向链表, 称为x的孩子链表. 孩子链表中的每个孩子y均有指针y.left和y.right, 分别指向y的左兄弟和右兄弟. 如果y是仅有的一个孩子, 则y.left = y.right = y. 孩子链表中各兄弟出现的次序任意.
- 每个结点有另外两个属性: x.degree表示x的孩子链表中的孩子数目. x.mark表示x自从上一次成为另一个结点的孩子后, 是否失去过孩子.新产生的结点是未被标记的, 并且当结点x成为另一个孩子时, 更新为未被标记结点.
- 指针H.min指向堆H中具有最小关键字的树的根结点. 若不止一个根结点具有最小关键字, 则这些根结点中的任何一个都有可能成为最小结点. 若H为空, 则H.min为NIL.
- 所有树的根也用left和right指针连接成一个环形的双链表, 称为斐波那契堆的根链表. 根链表中的树次序可以任意.
- H.n表示H中当前的结点数目.
19.2 可合并堆操作
斐波那契堆上的一些可合并堆操作要尽可能长地延后执行, 不同的操作可以进行性能平衡.
创建一个新的斐波那契堆
def make_fib_heap(): 分配并返回一个斐波那契堆对象H H.n = 0 H.min = NIL
实际代价O(1), 摊还代价O(1).
插入一个结点
# 将结点x插入斐波那契堆H中# 假定该结点已经被分配, x.key已经赋值def fib_heap_insert(H, x): x.degree = 0 x.p = None x.child = None x.mark = False if H.min is None: # create a root list for H containing just x H.min = x else: # insert x into H's root list if x.key < H.min.key: H.min = x H.n = H.n + 1
实际代价O(1), 摊还代价O(1).
寻找最小结点
直接通过H.min得到, 实际代价O(1), 摊还代价O(1).
两个斐波那契堆的合并
# 合并斐波那契堆H1和H2, 并在该过程中销毁H1和H2def fib_heap_union(H1, H2): H = make_fib_heap() H.min = H1.min # concatenate the root list of H2 with the root list of H if (H1.min is None) or (H2.min is not None and H2.min.key < H1.min.key): H.min = H2.min H.n = H1.n + H2.n return H
实际代价O(1), 摊还代价O(1).
抽取最小结点
def fib_heap_extract_min(H): z = H.min if z is not None: for x in z.childlist: # add x to the root list of H x.p = None # remove z from the root list of H # assume the fields of z remain if z == z.right: H.min = None else: H.min = z.right consolidate(H) H.n = H.n - 1 return z
没有辅助过程consolidate也能满足斐波那契堆的性质, 但是根链表会越来越长, 使得整个堆几乎就是一个链表, 那些尽可能延后的工作的性能就不能平衡了, 因此需要通过consolidate过程来合并H的根链表, 减少链表上根的数目.
# 合并H的根链表, 减少斐波那契堆中树的数目.# 重复以下步骤直到根链表中的每一个根有不同的度数# 1.在根链表中找到两个具有相同度数的根x和y, 假定x.key<=y.key# 2.把y链接到x.def consolidate(H): let A[0...D(H.n)] be a new array # D(H.n)是最大度数的上界 for i in range(D(H.n)+1): A[i] = None for w in H.rootlist: x = w d = x.degree while A[d] is not None: y = A[d] if x.key > y.key: swap(x,y) fib_heap_link(H,y,x) A[d] = None d = d + 1 A[d] = x H.min = None for i in range(D(H,n)+1): if A[i] is not None: if H.min is None: # create a root list for H containing just A[i] H.min = A[i] else: # insert A[i] into H's root list if A[i].key < H.min.key: H.min = A[i]
def fib_heap_link(H, y, x): # remove y from the root list of H # make y a child of x, incrementing x.degree y.mark = False
fib_heap_extract_min摊还代价为O(D(n)), 而D(n) = O(lgn), 因此摊还代价为O(lgn).
19.3 关键字减值和删除一个结点
关键字减值
def fib_heap_decrease_key(H, x, k): if k > x.key: error("new key is greater than current key") x.key = p y = x.p if (y is not None) and (x.key < y.key): cut(H, x, y) cascading_cut(H, y) if x.key < H.min.key: H.min = x def cut(H, x, y): # remove x from the child list of y # decrement y.degree # add x to the root list of H x.p = None x.mark = False
def cascading_cut(H, y): z = y.p if z is not None: if y.mark == False: y.mark = True else: cut(H, y, z) cascading_cut(H, z)
摊还代价O(1).
删除一个结点
def fib_heap_delete(H, x): fib_heap_decrease_key(H, x, -inf) fib_heap_extract_min(H)
摊还时间为O(D(n))即O(lgn).