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

formatuu

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