python 诠释 堆排序
最近在使用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 >= list :
largest = lt
if rt <= size and list >= list :
largest = rt
if largest != index :
temp = list
list = list
list = 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
if length >= 2:
list = list
list = 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 =
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 以后 然后把最后一个数据赋值给第一个
数据 这样就不会对其余数据的顺序造成影响 只需要对第一个数据进行一次 堆调整就好了……
堆排序在记录较少时不值得提倡，但是在大数据量时还是很有效的 ……
页:
[1]