圖論演算法ch19–2 — Fibonacci Heaps

前情提要

Mergeable Heap

凡是支援
Make-Heap(), Insert(H, x), Minimum(H), Extract-Min(H), Union(H1, H2)
的資料結構，都算是mergeable heap

Binomial Heap

請參考ch19–1

圖論演算法Ch19–1 — Binomial Heaps

正題開始

什麼是 Fibonacci Heaps？

基本定義

1. rooted tree
2. 父的值≤子的值
3. 除了mergeable heap的五種operation
   還有Decrease-Key(H, x, k)、Delete(H, x)

相關知識

1. 有mark[x]：用來記錄，是否失去過兒子
2. Potential function：t(H) + 2m(H)
   t(H)是root的個數
   m(H)是mark的個數
3. 假設maximum degree D(n)已知
   這個假設在後面很重要
4. 表示方法會造成root list(可以逛一圈)

Fibonacci Heap

比較(看看就好)

Fibonacci-Heaps Operations

cost = 真正的cost+增加的存款
增加的存款 = potential function(H’)-potential function(H)

1.Make-Fib-Heap() ->建一個空的heap
step1. 令n[H] = 0
step2. 讓min[H] = null

potential function(H)：0
cost(花費)：O(1)

2. Fib-Heap-Insert(H, x) -> 將 x insert至 H
step1. 建只包含x的heap Hx
step2. 將H和Hx連接在一起
step3. 小的當min
step4. n[H]+=1//個數加一

potential function(H’)-potential function(H)：1
cost(花費)：O(1)

Fib-Heap-Insert(H, 21)

3. Minimum(H) ->找到最小值min
step1. 直接return pointer

potential function(H)：0
cost(花費)：O(1)

4. Fib-Heap-Union(H1, H2) ->把H1, H2 union在一起
step1. 將H1, H2 的 root list 連在一起
//就是把指標改一改就好了
step2. min[H1] vs min[H2]，小的當min

potential function(H’)-potential function(H)：0
cost(花費)：O(1)

5. Fib-Heap-Extract-Min(H) ->回傳最小值min 並刪除
step1. return pointer拿到最小值z
step2. 將z的兒子都放到root list
step3. 將z從root list移走
step4. 若只有z一個，min[H]=null，否則，做合併的動作

合併的目標：讓每一個root的degree都不相同
step1. 找兩個degree相同的root
step2. 將他們合併，小的當root

會用到一個陣列來記錄degree對應的root

Fib-Heap-Extract-Min(H)

potential function(H’)：(D(n)+1) + 2m(H)
cost(花費)：O(D(n))

這裡會多用到兩個function
1. Fib-Heap-Link(H, y, x)：用來把點放到root list
2. Consolidate(H)：用來合併相同的degree

6. Fib-Heap-Decrease-Key(H, x, k) ->把k的值變小
step1. 如果k<x的值，將x移到root，否則error(就不做了)
step2. Cut(H, x, y) //y是x的parent
step3. Cascading-Cut(H, y)
step4. 確認誰才是min

Cut(H, x, y)->搬到root list
step1. 將x移到root list
step2. 將x設成白色(mark=false)

Cascading-Cut(H, y)
->一直往上檢查，每人最多失去一個孩子，若超過，移到root list

Fib-Heap-Decrease-Key(H, x, k)

potential function(H’)-potential function(H)：4-c
cost(花費)：O(1)

7. Fib-Heap-Delete(H, x) ->把x刪掉
step1. 把x變成負無限大
step2. 刪除最小

cost(花費)：O(1)+O(D(n))

所有的code

Fib-Heap-Insert(H, x)

Fib-Heap-Union(H1, H2)

Fib-Heap-Extract-Min(H)

Fib-Decrease-Key(H, x, k)