主題

CH. 1.0 - Heap

鄧董 | 2020-09-20 02:48:35 | 巴幣 2 | 人氣 739

原本想先從Fibonacci heap著手，突然想到heap本身其實也很值得紀錄一番，遂由此而起。

Heap : 中文又稱"堆積"，常見的為二元堆積(Binary Heap)，是一由大到小 or 由小到大的二元樹結構。

Mergeable : 任何data structures可以支援以下5種操作，且所有elements都有key;

MAKE-HEAP ()
INSERT (H , x)
MINIMUM (H)
EXTRACT-MIN (H)
UNION (H1 , H2)

Heap property : H[ Parent(i) ] ≤ or ≥ H[ i ] , ∀ i ∈ Index

Heap最簡單的實作方式為使用array，可說是相當簡單就能使用並廣泛運用在任何需要的地方，以下都以array implement。

Note : 由於應對之後使用多是為minimum form，所以以下思路以此為主；log底數皆為2。

Heapify的精神 : 把一node所有children與其相比，如果較大/小就把index存起來，遍歷完成後檢查index是否跟parent相符，不符就互換，並遞迴執行Heapify(H , index)。

HEAPIFY (H , i)

l = LEFT (i)
r = RIGHT (i)
if l ≤ H.heap-size and H[ l ] < H[ i ]

smallest = l

else smallest = i
if r ≤ H.heap-size and H[ r ] < H[ smallest ]

smallest = r

if smallest ≠ i

exchange H[ i ] with H[ smallest ]

HEAPIFY (H , smallest)

Recurrence : T (n) ≤ T (2n/3) + Θ (1)

Note : 2n/3為worst case，tree的一邊half-full situation.

Time complexity : O (log n)

從recurrence可得出 or Master theorem。

Build-Heap的精神 : 利用上述的Heapify，給定heap-size來建構一個heap。

BUILD-MIN-HEAP (H)

H.heap-size = H.length

for i = H.length/2 downto 1

HEAPIFY (H , i)

Recurrence : T (n) ≤ 2T (n/2) + log n

Note : 由root開始，h=1有兩個nodes，故要multiply by 2，其餘依此類推。

Time complexity : O (n)

證明 (從recurrence得出 or 根據heap大小--leaf*height--得出)。

HeapSort 的精神 : 把最後一個element與root交換，提出最後一個element後再對root做Heapify，重複到最後可得出由大到小的排列。

HEAPSORT (H)

BUILD-MIN-HEAP (H)

for i = H.length downto 2

exchange H[ 1 ] with H[ i ]

H.heap-size --

HEAPIFY (H , 1)

Time complexity : O (nlog n)

Build-Heap使用了O (n)，for迴圈使用了n-1次，而Heapify為 log n，其餘為constant time，故為 O (n) + (n - 1)*(log n +C) = O (nlog n)

Priority queues : 一種data structure處理 set，作為heap的一種延伸應用，可以處理INSERT、MINIMUM、EXTRACT-MIN、INCREASE-KEY等operations。

Note : priority queue應用層面相當廣泛，課本中舉例為event-driven simulator，使用Extract Min 來選擇優先發生的事件作處理，Insert把新事件插入priority queue中；或是scheduler、pipeline manager之類需要取前後順序的系統都能使用上，而且在插入、刪除node的速度不慢，也適合套用在各類演算法中。