斐波那契堆（Fibonacci Heap）
1. 定義
FibHeap是一個樹的集合，且樹滿足最小堆性質，根表不要求樹根的度有序，head指向根表中值最小
的結點，全部使用雙向回圈鏈表，
KEY：防止超出O(lgn)的操作出現，也即防止出現度超過O(lgn)的樹出現，只要能保證D(n)<=
lgn，其性能優于二項堆，
2. 資料結構
- 結點的域
p：父指標
left,right：左右指標
key：值
degree：度
child：指向任意孩子
mark：非常重要的標志位，創建結點或結點成為孩子時，mark=false，結點失去一個孩子時，mark=true， - 根表以及結點間 雙向回圈鏈表
3. 預定義
- 勢函式定義
f(H)=t(H)+2m(H)
f表示勢函式，t表示樹的個數，m表示mark=true的結點數， - 平攤分析
C^i = C_i + f(i) - f(i-1)
C^i：平攤成本
C_i：操作的實際成本
f(i-1):操作前的勢能
f(i):操作后的勢能 - 任意結點的最大度上界 D(n)
- 無序二項樹U_k
不要求按子樹的度的大小排列，
4. 五個基本操作
- 創建空堆
- 插入結點x
將x作為U_0樹插入根表，檢查head， x.mark=false，
平攤分析：
C_i = O(1)
f(i)-f(i-1)=t(H')-t(H)+2m(H') -2m(H)=1+0=1
則C^i=O(1) - 查找最小值結點
head
平攤成本O(1) - 合并堆
step1:合并根表
step2：檢查head
平攤成本O(1) - 抽取最小值結點z
平攤成本O(D(n))
- 將z的子樹插入根表
- delete z, head隨意指
- 清理根表，防止根表過大，合并相同度的樹，重構堆，并將head指向最小結點，
使用一個輔助指標陣列A[0,..., D(n[H])]，高效合并和重構堆，D(n[H])表示根結點的最大度，
陣列下標表示度，陣列元素為根節點指標，初始化為null，合并度相同的樹，最終使根表中的度是
唯一的，
注意：以head為起點，向右掃描根表，同時合并相同度的二項樹，直到根表中的樹具有唯一的度，
5.兩個擴展操作
- 結點減值
- 根結點減值后不需要后續操作
- 非根結點x減值后如果破壞了最小堆性質，則需要后續操作
- 切斷x與其父結點y的關系，把x加入根表，x.mark=Flase
- 級聯切斷 遞回檢查y結點，如果x是它被剪掉的第二個孩子(y.mark=TRUE)，則y也從原
樹中脫離，加入根表，同時y=y.p，繼續檢查，直到y.mark=false或y=root - 別忘記重新確定head->min
fibHeap_decrease(h, x, k):
if k > x.KEY:
error
return
x.key = k
y = x.p
if y is not None and x.key < y.key:
# 切 x
cut(h, x, y)
# 級聯切斷
cascading_cut(H, y)
# 檢查head
if x.key < h.min.key :
h.min = x
cut(h,x,y):
remove x from y
y.degree -= 1
add x to rootlist
x.p = None
# 關鍵
x.mark = FALSE
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)
- 洗掉結點
- x結點減值到MIN
- 抽取最小值
參考
《演算法導論》
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/79578.html
標籤：其他
上一篇：啟發式演算法之遺傳演算法
下一篇：跟我一起學演算法——動態規劃