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[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 以后 然后把最后一个数据赋值给第一个 

数据 这样就不会对其余数据的顺序造成影响 只需要对第一个数据进行一次 堆调整就好了……

 

堆排序在记录较少时不值得提倡，但是在大数据量时还是很有效的 ……

评论

1 楼 最佳蜗牛 2013-09-03  

好用必须赞