python heap sort

#!/usr/bin/env python
 
from heapq import heappush, heappop
 
if __name__ == "__main__":
    # Simple sanity test
    heap = []
    data = [1, 3, 5, 7, 9, 2, 4, 6, 8, 0]
    for item in data:
        heappush(heap, item)
    sort = []
    while heap:
        sort.append(heappop(heap))
    print sort

一个heap要满足paren < leaf, root是最小的

heappush

1、append新的值在数组的结尾

2、再把结尾处的节点放到合适的位置，这个位置是通过跟heap里parent节点比较得来

      

heappop

1、把root(最小值)pop

2、把结尾节点的值insert到第一个root节点的位置

3、再调整这个root节点的位置，这个位置是通过跟heap里child节点比较得来