排序算法学习（python版本）之堆排序（HeapSort）

Contains:
堆排序以及堆排序的应用
堆排序（Heapsort）是指利用堆積這種資料結構所設計的一種排序算法。堆積是一個近似完滿二元樹的結構，並同時滿足堆積的性質：即子結點的键值或索引總是小於（或者大於）它的父節點。

• 最差时间复杂度：O(nlogn)
• 最优时间复杂度：O(nlogn)
• 平均时间复杂度：O(nlogn)

建立堆，保持最大堆，堆排序（顶端最大元素与最后一个元素不断的交换）——整个过程。

#-*-coding:utf-8-*-

def heap_sort(lst):
    for start in range((len(lst)-2)/2, -1, -1):
        siftdown(lst,start,len(lst)-1)
    for end in range(len(lst)-1, 0, -1):
        lst[end], lst[0] = lst[0], lst[end]
        siftdown(lst, 0, end - 1)
    return lst

def siftdown(lst, start, end):
    root = start
    while True:
        child = 2*root + 1
        if child > end:break
        if child+1<=end and lst[child] < lst[child+1]:
            child += 1
        if lst[child] > lst[root]:
            lst[child],lst[root] = lst[root],lst[child]
            root=child
        else:
            break
           
def main():
    l=[3,4,1,8,2,9,6,5,7,10]
    print heap_sort(l)

if __name__ == '__main__':
    main()

使用heapq

#!/usr/bin/env python
#-*-encoding:utf-8-*-
from heapq import heappush,heappop

def heap_sort(iterable):
    h = []
    for value in iterable:
        heappush(h, value)
    return [heappop(h) for i in range(len(h))]

def main():
    L = [1, 3, 5, 7, 9, 2, 4, 6, 8, 0]
    print heap_sort(L)

if __name__ == "__main__":
    main()

参考资料：
http://zh.wikipedia.org/wiki/%E5%A0%86%E6%8E%92%E5%BA%8F
http://blog.csdn.net/v_july_v/article/details/6198644
http://docs.python.org/2/library/heapq.html
http://rosettacode.org/wiki/Sorting_algorithms/Heapsort
http://en.wikipedia.org/wiki/Heapsort