python实现最小堆(TOP N 问题)

top N问题可以使用最小堆来实现

一下程序实现了从用户输入的一系列数字中，选出最大的N个数字(不是堆排序)

 

#!/usr/bin/env python
#coding=utf-8
#heapsort.py
import sys
import stdinInput
def heapsort(sortarray,topN):
    sortarraylen=len(sortarray)
    heaparray=[]
    for i in xrange(0,sortarraylen):
        if len(heaparray)<=topN:
            heaparray.append(sortarray[i])
            heapinsertadjust(heaparray,i)
        else:
            if sortarray[i]>heaparray[0]:
                heaparray[0]=sortarray[i]
                heapdeleteadjust(heaparray,0)
    return heaparray
#调整初始最小堆
def heapinsertadjust(sortarray,beginnode): 
    rootnode=beginnode;
    while(rootnode>0):
        parentNode=(rootnode-1)/2
        if sortarray[rootnode]<sortarray[parentNode]:
            sortarray[rootnode],sortarray[parentNode]=sortarray[parentNode],sortarray[rootnode]
        rootnode=parentNode
#最小堆构造完成后，再来满足条件的数据就需要删除掉节点
def heapdeleteadjust(sortarray,nodeid):
    currentminid=nodeid
    sortarraylen=len(sortarray)
    if (nodeid*2+1)>=sortarraylen:
        return;
    if (nodeid*2+2)<sortarraylen:
        currentminid=currentminid*2+1 if sortarray[currentminid*2+1]<sortarray[currentminid] else currentminid
        currentminid=nodeid*2+2 if sortarray[nodeid*2+2]<sortarray[currentminid] else currentminid
        if currentminid!=nodeid:
            sortarray[currentminid],sortarray[nodeid]=sortarray[nodeid],sortarray[currentminid]
            heapdeleteadjust(sortarray,currentminid)
        else:
            return
    else:
        if sortarray[currentminid*2+1]<sortarray[currentminid]:
            sortarray[currentminid*2+1],sortarray[currentminid] = sortarray[currentminid],sortarray[currentminid*2+1]
        return

if __name__=='__main__':
    style=5
    try:
        style=int(sys.argv[1]) 
    except:
        print "input argv error, use 5 as Number of bottom"

    stdinInput.stdinInput()
    intsortArrays=heapsort(stdinInput.intsortArrays,style)
	
    print intsortArrays