python 诠释 堆排序

yesn

　　最近在使用java 的PriorityBlockingQueue 发现其排序使用的是堆排序 ，于是借这个周末翻了一下大学时候的数据结构的书好好复习了下，堆排序是一种选择排序，堆的定义： n各元素的序列{k1, k2, k3, ……kn}，当且仅当满足ki <= k2i  &&   ki <= k2i + 1(小顶堆) 或者 ki >= k2i && ki >= k2i+1(大顶堆) 的关系时，称之为堆。

　　如何构建这样的一个堆呢？ 
　　我们现在有这样的一个序列 :
　　{49,38,65,97,76,13,27,49}  , 反映成二叉树就是：

　　我们可以将此树按非终端结点分成4个部分 ，  按 index 为 4，3 ， 2 ， 1 的四个顶部节点 自低向上对每个部分按堆的规则进行调整 最后就可以得到一个堆：

def heap_adjust(list,index):
size = len(list)
lt = index * 2
rt = index * 2 + 1
largest = index
if lt <= size and list[lt-1] >= list[largest-1] :
largest = lt
if rt <= size and list[rt-1] >= list[largest-1] :
largest = rt
if largest != index :
temp = list[index-1]
list[index-1] = list[largest-1]
list[largest-1] = temp
heap_adjust(list,largest)
def build_heap(list):
length = len(list)
for index in range(length/2,0,-1):
heap_adjust(list,index)
def heap_pop(list):
r = None
length = len(list)
if length >= 1:
r = list[0]
if length >= 2:
list[0] = list[length-1]
list[length-1] = None
list.remove(None)
heap_adjust(list,1)
return r
def heap_append(list,item):
list.append(item)
build_heap(list)
if __name__ == '__main__':
list = [49,38,65,97,76,13,27,49]
build_heap(list)
print list
heap_append(list,100)
print list
length = len(list)
for i in range(length):
print '%d ' % heap_pop(list),
　　heap_adjust 方法的作用是对每个部分按堆的规则进行调整，在pop 数据时 把第一个数据pop 以后 然后把最后一个数据赋值给第一个 
　　数据 这样就不会对其余数据的顺序造成影响 只需要对第一个数据进行一次 堆调整就好了……
　　堆排序在记录较少时不值得提倡，但是在大数据量时还是很有效的 ……