时间:2021-05-23
Python heapq 详解
Python有一个内置的模块,heapq标准的封装了最小堆的算法实现。下面看两个不错的应用。
小顶堆(求TopK大)
话说需求是这样的: 定长的序列,求出TopK大的数据。
import heapqimport randomclass TopkHeap(object): def __init__(self, k): self.k = k self.data = [] def Push(self, elem): if len(self.data) < self.k: heapq.heappush(self.data, elem) else: topk_small = self.data[0] if elem > topk_small: heapq.heapreplace(self.data, elem) def TopK(self): return [x for x in reversed([heapq.heappop(self.data) for x in xrange(len(self.data))])]if __name__ == "__main__": print "Hello" list_rand = random.sample(xrange(1000000), 100) th = TopkHeap(3) for i in list_rand: th.Push(i) print th.TopK() print sorted(list_rand, reverse=True)[0:3]大顶堆(求BtmK小)
这次的需求变得更加的困难了:给出N长的序列,求出BtmK小的元素,即使用大顶堆。
算法实现的核心思路是:将push(e)改为push(-e)、pop(e)改为-pop(e)。
感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!
声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。
Python操作MySQL详解及实例使用Python进行MySQL的库主要有三个,Python-MySQL(更熟悉的名字可能是MySQLdb),PyMySQL和
本文实例讲述了Python图算法。分享给大家供大家参考,具体如下:#encoding=utf-8importnetworkx,heapq,sysfrommatp
Javascript实现计算器:系列文章:JS实现计算器详解及实例代码(一)Javascript实现计算器时间功能详解及实例(二)小型JavaScript计算器
Javascript计算器:系列文章:JS实现计算器详解及实例代码(一)Javascript实现计算器时间功能详解及实例(二)Javascript计算器->添加
java仿Servlet生成验证码实例详解实现原理:使用BufferedImage对象的Graphics来进行绘制,然后输出成一张图片进行保存实现代码及详解:p