Maintain a fixed size heap -python

Solution 1:

There's no built-in in heapq to check the size, so you'll have to do that 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 a min heap, not a max heap. You'll need to reverse the order of your priorities, probably by negating them.

Solution 2:

I found this post I was trying to implement a top-n heap with fixed size, here is the solution I can offer:

from heapq import heapify, heappush, heappushpop, nlargest

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)

and more optimally (thanks to @CyanoKobalamyne)

from heapq import heapify, heappush, heappushpop, nlargest

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 nlargest(self.length, self.h)

Solution 3:

If you want the k smallest elements, which is equivalent to discarding the largest element of a fixed-size min-heap on every push, you should use heapq.nsmallest (or heapq.nlargest for the opposite) on the iterable from which you are building the heap.

Solution 4:

Python (as of today v 3.8x) does not have a built in fixed heap size functionality. You have 2 options:

1. maintain a heap and on every push, check if size > fixedSize then pop. This means at any given time, the max size of your heap could be fixedSize+1 which is when you'll pop one.

2. Another option is to use heapq.heapreplace(heap, item) which as per the docs :

Pop and return the smallest item from the heap, and also push the new item. The heap size doesn’t change. If the heap is empty, IndexError is raised. This one step operation is more efficient than a heappop() followed by heappush() and can be more appropriate when using a fixed-size heap.