Python heapq使用详解及实例代码
2019/7/13 23:16:44
本文主要是介绍Python heapq使用详解及实例代码,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
Python heapq 详解
Python有一个内置的模块,heapq标准的封装了最小堆的算法实现。下面看两个不错的应用。
小顶堆(求TopK大)
话说需求是这样的: 定长的序列,求出TopK大的数据。
import heapq import random class 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)。
class BtmkHeap(object): def __init__(self, k): self.k = k self.data = [] def Push(self, elem): # Reverse elem to convert to max-heap elem = -elem # Using heap algorighem 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 BtmK(self): return sorted([-x for x in self.data])
感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!
这篇关于Python heapq使用详解及实例代码的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-08有遇到过吗?同样的规则 Excel 中 比Python 结果大
- 2024-03-30开始python成长之路
- 2024-03-29python optparse
- 2024-03-29python map 函数
- 2024-03-20invalid format specifier python
- 2024-03-18pool.map python
- 2024-03-18threads in python
- 2024-03-14python Ai 应用开发基础训练,字符串,字典,文件
- 2024-03-13id3 algorithm python
- 2024-03-13sum array elements python