首页 > 代码库 > 【剑指offer】 堆排序查找最小的K个数
【剑指offer】 堆排序查找最小的K个数
上一篇 说了些堆的建立及其相关操作,这里看下用堆来解决数据量较大的时候,查找最小的k个数的情况。这里会用到上一篇中的函数。
我们先生存1千万个随机数,写到文件中:
import random def randData(): with open('randint.txt', 'w') as fd: for i in range(1, 10000000): fd.write('%d ' %random.randint(1, 100)) if i % 100 == 0: fd.write('\r')
import sys def findMinK(k, filename = 'randint.txt'): #init heapk with max int heapk = [sys.maxint] * k with open('randint.txt', 'r') as fd: line = fd.readline().strip().split() for i in range(len( line )): if heapk[0] > int( line[i] ): heapk[0] = int( line[i] ) fixDown(heapk, 0, k, ls = 0) print heapk
这里是将堆用最大值初始化了,当然应该是从0开始插入,如果还没到k个,就直接插入,不用比较,否则要进行比较,这里为了方便,直接初始化了。
结果用了15 s,python慢,还是机器慢,狠心2块钱买个彩票,还被巴西坑了。。。。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。