1，什么是二叉堆？
1），父节点总是大于等于（或者小于等于）子节点。
2），每个节点及其部分都是一个二叉堆。
3），他是一个完全二叉树。
2，堆排序。
1），调整堆，首先排序序列是一个物理上的顺序存储表，逻辑上的完全二叉树。调整为二叉堆的方式就是从最后一个非叶子节点（N/2-1）开始调整为满足二叉堆的性质。
2），堆排序。就是记录第一节点根节点的值，把最后一个替换第一值，重新调整新的堆步骤1），直到剩下最后一个元素。时间复杂度为O（N*logN）。
3），python简单实现。（python2.7）
#!/usr/bin/env python
# -*- coding:utf-8 -*-
#the max heap
def MaxHeapAdjust(dist):
length=len(dist)
halflen=length/2-1
for index in range(halflen,-1,-1):
leftindex=2*index
rightindex=2*index+1
if leftindex>=length:
break
if dist[index]<dist[leftindex]:
templ=dist[index]
dist[index]=dist[leftindex]
dist[leftindex]=templ
#MaxHeapAdjust(dist)
if rightindex>=length:
break
if dist[index]<dist[rightindex]:
temp2=dist[index]
dist[index]=dist[rightindex]
dist[rightindex]=temp2
print "adjust:%s"%str(dist)
return dist
#the min Heap
def MinHeapAdjust(dist):
length=len(dist)
halflen=length/2-1
for index in range(halflen,-1,-1):
leftindex=2*index
rightindex=2*index+1
if leftindex>=length:
break
if dist[index]>dist[leftindex]:
templ=dist[index]
dist[index]=dist[leftindex]
dist[leftindex]=templ
#MaxHeapAdjust(dist)
if rightindex>=length:
break
if dist[index]>dist[rightindex]:
temp2=dist[index]
dist[index]=dist[rightindex]
dist[rightindex]=temp2
return dist
def MaxHeapSort(dist):
result=[]
while len(dist)>0:
re=MinHeapAdjust(dist)
result.append(re[0])
re[0]=re[-1]
dist=dist[0:len(dist)-1]
#result.append(result[])
return result
def MinHeapSort(dist):
result=[]
while len(dist)>0:
re=MaxHeapAdjust(dist)
result.append(re[0])
re[0]=re[-1]
dist=dist[0:len(dist)-1]
return result
def HeapSort(dist,type="asc"):
if type=='asc':
dist=MaxHeapSort(dist)
else:
dist=MinHeapSort(dist)
return dist
if __name__=="__main__":
dist=[1,2,3,56,45,66,45,32,87,34]
print HeapSort(dist)
print "----------------------------"
dist=[1,2,3,56,45,66,45,32,87,34]
print HeapSort(dist,'desc')