目錄
- 1.二叉堆(Binary Heap)、二項堆、斐波那契堆(簡稱Fib堆)的比較：
- 2. 二項樹
- 2.1 定義
- 2.2 二項樹B_k的性質
- 3. 二項堆
- 3.1 定義
- 3.2 資料結構
- 3.3 操作
- 3.3.1 五個基本操作
- 3.3.2 兩個擴展操作
- 參考
1.二叉堆(Binary Heap)、二項堆、斐波那契堆(簡稱Fib堆)的比較：
相同：
- 都是可歸并堆（Mergeable Heap）；
- 它們都支持5個基本操作（創建、插入、查找最小值、抽取最小值、合并堆）和2個擴展操作
（結點減值、結點洗掉），
不同：
- 二叉堆是一種結點有序的完全二叉樹，可采用陣列結構存盤，通過陣列下標索引結點，分最大
堆和最小堆， 二項堆和Fib堆都是最小堆， - 二項堆由二項樹組成，結構比二叉堆復雜，但其堆合并操作的時間復雜度較好，當堆合并操作
較多時，可使用二項堆，反之，使用二叉堆即可，
2. 二項樹
2.1 定義
僅包含一個結點的有序樹是一棵二項樹(B_0樹)，二項樹B_k由兩棵B_{k-1}樹組成，其中一
棵B_{k-1}樹的根作為另一棵B_{k-1}樹根的最左孩子(k≥0)，
2.2 二項樹B_k的性質
- 結點數 n = 2{^k}
- 樹高為 k = lgn
- 深度為i處有k!/(i!(k-i)!）個結點（k>=i>=0），
- 根的度最大為k，若根的孩子從左到右編號為k-1,k-2,…,1,0，則孩子i恰好是子樹B_i的根，
proof：主要依靠B_k與B_{k-1}間的關系
- 2^{k-1} + 2^{k-1} = 2^{k}
- k-1+1 = k
- 即證D(k,i) = D(k-1,i-1) + D(k-1,i)
[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-x0BE2UNK-1582727656770)(img/binomialHeap-math1.png)]
3. 二項堆
3.1 定義
它是由一系列二項樹組成的集合，滿足以下性質：
堆中每一顆二項樹都滿足最小堆性質，堆中度為k的樹是唯一的 => n個結點的二項堆中最多有
lgn上界 + 1課二項樹
3.2 資料結構
-
根表 root list
head[H]->B_0->B_2->B_3
根表是單鏈表，它鏈接所有二項樹的根結點，且按度的遞增順序鏈接， -
結點 node
每個結點包含5個域：
key：資料
指標p：指向父結點
degree（度）：孩子個數
child：指向最左孩子
sibling：指向右兄弟
class Node():
"""
class of the node in the heap
provide functions to the binomial tree
"""
def __init__(self, key = None):
self.p = None # point to parent
self.key = key # value
self.degree = 0 # count of the children
self.child = None # point to child of the left
self.sibling = None # point to the right brother
def link_tree(self, other):
"""
other -> subtree of self.
"""
other.parent = self
other.sibling = self.child
self.child = other
self.degree += 1
3.3 操作
3.3.1 五個基本操作
-
創建空堆
-
取最小值：由于二項樹滿足最小堆性質，所以遍歷根表即可，
-
合并兩個二項堆
step1：按照二項樹的度遞增的順序合并兩個根表，
step2：根表調整，以滿足度的唯一性，用三個輔助指標（per、p、after）將度重復的樹合并，
由于step1合并后的根表中，度相同的樹最多有兩顆，所以會出現以下幾種情況：
case1：三個指標所指二項樹根都存在，且度不同 => 指標后滑，進入case3或結束，
case2：per為空，p.degree = after.degree，且after.sibling存在 =>指標后滑，進入case4，
case3：case1或case2不成立，若pre為空，則一定有p.degree = after.degree => 根據degree
合并p和after所指二項樹，after后滑，進入case2 或 case1
case4：三個指標所指二項樹根都存在，且度相同 =>根據degree合并p和after所指二項樹，after
后滑，進入case3，時間復雜度分析：
- 合并根表 O(lgn)
- 根表調整，遍歷新根表O(lgn)
- 合并操作的時間復雜度為O(lgn)，優于二叉堆的O(n)
def _merge_rootlist(self, heap2):
"""
merge two root list and keep increasing order in degree.
"""
p1 = self.head
p2 = heap2.head
if not p1: # p1 = None
return heap2.head
if not p2: # p2 = None
return self.head
if p1.degree <= p2.degree:
p = p1
p1 = p1.sibling
else:
p = p2
p2 = p2.sibling
head = p
while p1 and p2:
if p1.degree <= p2.degree:
p.sibling = p1
p1 = p1.sibling
else:
p.sibling = p2
p2 = p2.sibling
p = p.sibling
if p2:
p.sibling = p2
else:
p.sibling = p1
return head
def _union(self, heap2):
"""
step1: merge two root list and keep increasing order in degree.
step2: adjust root(merge) to keep the unique of the degree in all
binomial trees.
use three point to adjust the heap: pre , p , after
"""
if heap2 is None:
return
if self.head is None:
self.head = heap2.head
self.size = heap2.size
return
# step1
head = self._merge_rootlist(heap2)
print("merge root list")
self.print_rootlist()
# step2 use three point to adjust the heap
if not head:
print("merge rootlist error")
return
pre = None
p = head
after = head.sibling
while after:
# case 1 / case 2 , point + 1
if p.degree != after.degree or (after.sibling is not None and
after.sibling.degree == p.degree ):
pre = p
p = after
# case 3, merge p and after into p
elif p.key <= after.key:
# update point
p.sibling = after.sibling
# merge two tree, p.child = after
p.link_tree(after)
else:
# after.degree == p.degree, after.sibling = None, p.key>after.key
# => update head ,link(after,p),over!
if pre == None:
head = after
# upfate pre.sibling = after, link(after,p)
else:
pre.sibling = after
after.link_tree(p)
p = after
after = p.sibling
self.head = head
self.size += heap2.size
return
- 插入結點x
將x放入一個空堆H2中，將H和H2合并，
時間復雜度為O(lgn)
def insert(self, node):
"""
insert a node into a null heap.
1. node->new heap (heap2)
2. union(self, heap2)
"""
h = BinomialHeap()
h.head = node
self.union(h)
self.size += 1
- 抽取最小值結點
step1：遍歷根表查最小值結點z，
step2：在根表中洗掉結點z，并把z的孩子"逆放"到一個空堆H2中，所謂逆放，即使H2滿足二項堆根
表中樹根的度遞增的順序，
step3：將H和H2合并，
時間復雜度O(lgn)
def extract_min_node(self):
self._extract_min_node()
return
def _extract_min_node(self):
size = self.size
min_node, pre_min = self.min()
self.extract(min_node, pre_min)
self.size = size - 1
return
def extract(self, node, pre_node):
if node == None:
return
# del min node in the root list
if pre_node==None:
self.head = min_node.sibling
else:
pre_node.sibling = node.sibling
# if the minimum node has no child
if(node.child == None):
return
# if the node has subtrees, then inesrt them into a new heap, and union this new heap with old heap.
new_heap = BinomialHeap()
# insert the subtrees in reverse order
p = node.child
list_root = []
while p.sibling != None:
p.parent = None
list_root.append(p)
p = p.sibling
list_root.append(p)
while list_root != []:
p = list_root.pop(-1)
new_heap.insert(p)
# union
self.union(new_heap)
return
3.3.2 兩個擴展操作
- 減值(減少結點z的key)
z減值后自底向上迭代比較，直到孩子結點的值大于父結點，類似冒泡，
時間復雜度；O(lgn)
def _decrease_key(self,node,key):
if node == None or node.key <= key:
print("node or key err")
return
node.key = key
x = node
p = node.p
# bubble
while p is not None and p.key > x.key:
t = p.key
p.key = x.key
x.key = t
x = p
p = p.p
return
- 洗掉結點z
step1:對z進行減值操作，將z的值減為最小值，
step2:對z所在二項樹的樹根執行抽取操作，
時間復雜度：O(lgn)
參考
《演算法導論》
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/79582.html
標籤：其他
上一篇：跟我一起學演算法——分治法
下一篇：「演算法01」排序演算法小結