Python heapq使用详解 Python heapq使用详解及实例代码
纯臻 人气:0想了解Python heapq使用详解及实例代码的相关内容吗,纯臻在本文为您仔细讲解Python heapq使用详解的相关知识和一些Code实例,欢迎阅读和指正,我们先划重点:Python,heapq,详解,Python,heapq妙用,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])
感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!
加载全部内容