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

13719654321

　　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)
heapinsertadjust(heaparray,i)
else:
if sortarray>heaparray[0]:
heaparray[0]=sortarray
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