Python heapq使用详解及实例代码
程序员文章站
2024-02-22 19:44:22
Python heapq 详解
Python有一个内置的模块,heapq标准的封装了最小堆的算法实现。下面看两个不错的应用。
小顶堆(求TopK大)
话说...
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])
感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!
上一篇: 解决python2.7用pip安装包时出现错误的问题
下一篇: java中文转全拼工具类分享