複習 max heap

發表於 更新於 分類於 Disqus：

最近想複習基本的資料結構，首先第一個想到還給老師就是 heap 了。所以就從 heap 開始。
這次實作的是 max heap，定義如下圖所示，max heap 為一個完整二元樹 (complete binary tree)，且每個父節點皆大於等於其左右子節點，由於完整二元樹的性質， max heap 資料結構可以很方便的使用陣列來表示。

假設陣列 index i 從 1 開始，heap 用陣列來表示又可以延伸出以下節點間的性質：

有了以上的節點性質，就可以很方便的應用在以下的實作。首先介紹max heap裡面最重要的部分 max heapify，給定一個元素的 index，由 top-down 的方式遞迴檢查該節點及其左右子節點有無符合 max heap 定義，若無則調整之。程式碼如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
def max_heapify(a, i, heap_size):
    left_i = 2 * i + 1
    right_i = 2 * i + 2

    if left_i < heap_size and a[i] < a[left_i]:
        biggest = left_i
    else:
        biggest = i
    if right_i < heap_size and a[biggest] < a[right_i]:
        biggest = right_i
    if biggest != i:
        a[biggest], a[i] = a[i], a[biggest]
        max_heapify(a, biggest, heap_size)

而 max heapify 設計上是針對該點以及左右子結點，依深度優先搜尋路徑調整成 max heap，如果 max heapify 的起始是根節點，依序要將整顆樹都調整成max heap，是會有其盲點的，因為這樣不會考慮整體的樹皆為 max heap，所以max heapify的起始點要從最小的父節點開始，以 bottom up 的方式由小到大來調整才可以確保整棵樹都符合max heap性質，程式碼如下所示。

1
2
3
4
5
# build max-heap
def build_max_heap(a, heap_size):
    for i in range(len(a)//2-1, -1, -1):
        max_heapify(a, i, heap_size)
    print(f'max heap: {a}')

len(a)//2-1 表示從最後位置的父節點開始往前做 max heapify。最後介紹 max heap 應用，由小到大排列的 heap sort，程式碼如下。

1
2
3
4
5
6
7
8
9
# heap sort
def heap_sort(a):
    heap_size = len(a)
    build_max_heap(a, heap_size)
    for i in range(len(a)-1, 0, -1):
        a[0], a[i] = a[i], a[0]
        heap_size -= 1
        max_heapify(a, 0, heap_size)
    print(f'heap sort: {a}')

原理為將 max heap tree 中的最大根節點與最後節點交換，接著縮小 heap size 範圍，呼叫 max heapify 調整，再繼續重複以上步驟直到所有陣列元素都調整過結束。
ref:

  1. https://web.stanford.edu/class/archive/cs/cs161/cs161.1168/lecture4.pdf