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)
heapinsertadjust(heaparray,i)
else:
if sortarray>heaparray:
heaparray=sortarray
heapdeleteadjust(heaparray,0)
return heaparray
#调整初始最小堆
def heapinsertadjust(sortarray,beginnode):
rootnode=beginnode;
while(rootnode>0):
parentNode=(rootnode-1)/2
if sortarray<sortarray:
sortarray,sortarray=sortarray,sortarray
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<sortarray else currentminid
currentminid=nodeid*2+2 if sortarray<sortarray else currentminid
if currentminid!=nodeid:
sortarray,sortarray=sortarray,sortarray
heapdeleteadjust(sortarray,currentminid)
else:
return
else:
if sortarray<sortarray:
sortarray,sortarray = sortarray,sortarray
return
if __name__=='__main__':
style=5
try:
style=int(sys.argv)
except:
print "input argv error, use 5 as Number of bottom"
stdinInput.stdinInput()
intsortArrays=heapsort(stdinInput.intsortArrays,style)
print intsortArrays
页:
[1]