Heap 資料結構簡介

Heap 是一種特別的完全二元樹。樹中的任意節點值與其子代節點值具有一定大小順序關係，這個特性稱作 Heap Property。

其中，如果每個節點值都大於其子代節點的特性，稱為 Max-Heap Property 。 具有 Max-Heap Property 的 Heap 稱為 Max-Heap 。 Max-Heap 的根節點值是該 Heap 資料堆中的最大值。

如果每個節點值都小於於其子代節點的特性，稱為 Min-Heap Property 。 具有 Min-Heap Property 的 Heap 稱為 Min-Heap 。 Min-Heap 的根節點值是該 Heap 資料堆中的最小值。

每次新增或移除一個節點，都會把該節點放到 root 來根據值來做交換結點動作，維持其特性(Min-Heap Property 或是 Max-Heap Property)。這個動作叫作 Heapify。每次 Heapify 都需要從 root 比到 leaf ，需要 O(logN) ，假設資料堆大小是 N。

假設是 Max-Heap 要找到其最大值其時間複雜度是 O(1)。
而逐步把 Max-Heap 的 root 移出，則可以得到該數據堆由大到小的排列。
每次移出，Heap 就做一次 heapify ，每次次 Heapify 需要 logN ，共要移動 N 次，所以時間複雜度是 O(NlogN)。

所以想要把資料做由小到大排序，只要把資料放入 MinHeap 再逐步 pop 出最小的值，這樣時間複雜度是 O(NlogN)。

這樣作法也稱作 Heap Sort。

實作

因為 Heap 是完全二元樹。
代表其排列資料是緊密排列，所以可以透過以下關係式把 Heap 用陣列來做實作

Parent(i):
  return Math.ceil(i/2) - 1
Left(i):
  return 2*(i +1) -1
Right(i):
  return 2*(i+1)

用陣列實作有一個好處是因為記憶體連續擺放，所以存取節點時，速度夠快。

以下是實作的 pesudo code:

Max Heapify 實作：

Max-Heapify(A, i) :
    l = Left(i), r = Right(i), largest = 0
    if l <= A.length and A[l] >= A[i]
       largest = l
    else largest = r
    if r <= A.length and A[r] >= A[largest]
       largest = r
    if largest !== i
       exchange A[i] with A[largest]
       Max-Heapify(A, largest)

Build Max Heap 實作

Build-max-heap(A):
    for i = Math.floor(A.length/2) downto 0
        Max-Heapify(A, i)

HeapSort 實作：

HeapSort(A):
    Build-max-heap(A)
    for i = A.length-1 downto 1
        exchange A[0] with A[i]
        remove last element of A
        Max-heapify(A, 0) 

參考文獻

https://docs.google.com/presentation/d/1eDHzVQVjyK54wn3QTX0RI2Eeqv1LVRsRH0iCP-Ch9g0/edit#slide=id.ge5a1bdd1ba_0_16