Geek Answers Handbook

Maintain a fixed-size heap -python

h = [] heapq.heappush(h,(10, 1200)) heapq.heappush(h,(20, 31)) heapq.heappush(h,(5, 1))

I want to keep a fixed heap size, say 3, so when I have heapq.heappush(h,(3,15)) , the key with the value 20 will be deleted and I will stay with the values ​​3,5 and 10. All ideas as?

+7
source share
2 answers

There is no built-in heapq to check the size, so you have to do it yourself:

 if len(h) < capacity: heapq.heappush(h, thing) else: # Equivalent to a push, then a pop, but faster spilled_value = heapq.heappushpop(h, thing) do_whatever_with(spilled_value)

Also note that heapq implements the minimum heap, not the maximum heap. You will need to reorder your priorities, possibly denying them.

+7
source

I found this post, I tried to implement top-n heaps with a fixed size, here is a solution I can offer:

 from heapq import heapify, heappush, heappushpop class MaxHeap(): def __init__(self, top_n): self.h = [] self.length = top_n heapify( self.h) def add(self, element): if len(self.h) < self.length: heappush(self.h, element) else: heappushpop(self.h, element) def getTop(self): return sorted(self.h, reverse=True)
0
source

More articles:


All Articles