Python heapq使用详解及实例代码
Pythonheapq详解
Python有一个内置的模块，heapq标准的封装了最小堆的算法实现。下面看两个不错的应用。
小顶堆（求TopK大）
话说需求是这样的：定长的序列，求出TopK大的数据。
importheapq importrandom classTopkHeap(object): def__init__(self,k): self.k=k self.data=[] defPush(self,elem): iflen(self.data)<self.k: heapq.heappush(self.data,elem) else: topk_small=self.data[0] ifelem>topk_small: heapq.heapreplace(self.data,elem) defTopK(self): return[xforxinreversed([heapq.heappop(self.data)forxinxrange(len(self.data))])] if__name__=="__main__": print"Hello" list_rand=random.sample(xrange(1000000),100) th=TopkHeap(3) foriinlist_rand: th.Push(i) printth.TopK() printsorted(list_rand,reverse=True)[0:3]
大顶堆（求BtmK小）
这次的需求变得更加的困难了：给出N长的序列，求出BtmK小的元素，即使用大顶堆。
算法实现的核心思路是：将push(e)改为push(-e)、pop(e)改为-pop(e)。
classBtmkHeap(object): def__init__(self,k): self.k=k self.data=[] defPush(self,elem): #Reverseelemtoconverttomax-heap elem=-elem #Usingheapalgorighem iflen(self.data)<self.k: heapq.heappush(self.data,elem) else: topk_small=self.data[0] ifelem>topk_small: heapq.heapreplace(self.data,elem) defBtmK(self): returnsorted([-xforxinself.data])
感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！