heapify algorithm

Data Structure 小練習，heapify 算法

關於 heap 更多內容請參考良葛格的精美筆記

感謝強者我同學 Unclehandsome ㄉㄉ指點 <(_ _)>

heap 的性質：

# Max heap
for all nodes in array:
    A[ parent(i) ] >= A[i]

用白文來講就是，

對於 heap 裏面的每一個 node ，他的 value 一定大於他子樹的任一節點的 value

並且他 left-subtree 跟 right-subtree 都要是 heap





簡記一下 make heap 的步驟：

make heap 的作法：想像一個空的 tree, 然後一次 insert 一個在 heap 的尾端

for nodes in array:
    insert node
    
insert:
    1:    append to the end of the heap (the last leaf)
    2:    compare with my parent
    3:    swap if i'm greater than my parent
    4:    goto 2

實作上要注意的地方是 tree 的 array index 從 1 開始 (算 node / 2 時比較好做)

#!/usr/bin/python

import random
import heapq

def mk_heap (arr):
    heap = ['']
    for i in arr:
        heap.append(i)
        l = len(heap) - 1
        while l >= 2 and heap[l] < heap[l//2]:
            heap[l], heap[l//2] = heap[l//2], heap[l]
            l = l // 2

    print heap[1:]


if __name__ == '__main__':
    arr = range (1, 20)
    random.shuffle(arr)
    brr = arr

    print "before heapify"
    print arr

    print "my make heap:"
    mk_heap(arr)

    h = []
    for i in brr:
        heapq.heappush(h, i)
    print "using heapq:"
    print h

Output:

before heapfy
[14, 11, 19, 2, 3, 10, 5, 13, 8, 15, 16, 1, 18, 9, 17, 4, 7, 6, 12]
my make heap:
[1, 3, 2, 4, 11, 5, 9, 7, 6, 15, 16, 19, 18, 10, 17, 14, 8, 13, 12]
using heapq:
[1, 3, 2, 4, 11, 5, 9, 7, 6, 15, 16, 19, 18, 10, 17, 14, 8, 13, 12]