Maintain a fixed size heap -python

Question

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

I want to maintain a fixed heap size of say 3,so when I next have heapq.heappush(h,(3,15)),key with value 20 gets deleted and I am left with values 3,5 and 10.Any ideas how?

Answer 1

There's no built-in in heapq function to check the size, so you'll have to do that yourself:

if len(h) < capacity:
    heapq.heappush(h, thing)
else:
    # pushes the element on and then pops off the top
    heapq.heappushpop(h, thing)

Note that heapq implements a min heap, not a max heap. You'll need to reverse the order of your priorities

I see that you specifically mentioned in your post that you would like a max heap with a fixed size of 3, and to be able to maintain the smallest elements when adding a new one in

By negating your elements on insertion into the min heap, you'll be able to use the heappushpop to your advantage. Instead of removing the smallest element and replacing it, you would now be removing the largest element and replacing it

This gives the disadvantage that as you pop elements off, you'll be seeing them in reverse order of size. So you'll have to negate them and reverse their order if you want a correctly ordered ascending list at the end of everything

Here is an illustration:

A visualization of pushpop when using the default minheap vs when negating the elements of the minheap

Here's an example of how it's implemented in a specific problem with the same requirements outlined in your post

Answer 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)

Answer 3

To achieve limited sized heap you could truncate your heap after every push operation.

limited_sized_heap = limited_sized_heap[:max_size_of_heap]

here is an example.

import random
import heapq

max_size_of_heap = 5
limited_sized_heap = []    

for i in range(10):
   a_random = random.randint(1,9)
   heapq.heappush( limited_sized_heap, a_random )
   limited_sized_heap = limited_sized_heap[:max_size_of_heap]
   print(limited_sized_heap)

outputs:

[3]
[3, 9]
[3, 9, 4]
[3, 4, 4, 9]
[2, 3, 4, 9, 4]
[1, 3, 2, 9, 4]
[1, 3, 1, 9, 4]
[1, 3, 1, 9, 4]
[1, 3, 1, 9, 4]
[1, 3, 1, 9, 4]

If you need absolute fixed sized heap instead of limited sized, you can just initial the heap with fixed-sized list with infinite values.

fixed_sized_heap = [float('inf')] * heap_size

Answer 4

I needed something like this myself, a sorted list of items with a maximum length.

I used a deque due to its 'maxlen' property.

import collections
import bisect

h = collections.deque(maxlen=3)

def insert(h, item):
    if len(h) < h.maxlen or item < h[-1]:
        if len(h) == h.maxlen:
            h.pop()
        bisect.insort_left(h, item)

>>> insert(h, 200); print(h)
deque([200], maxlen=3)

>>> insert(h, 100); print(h)
deque([100, 200], maxlen=3)

>>> insert(h, 200); print(h)
deque([100, 200, 200], maxlen=3)

>>> insert(h, 150); print(h)
deque([100, 150, 200], maxlen=3)

>>> insert(h, 200); print(h)
deque([100, 150, 200], maxlen=3)

>>> insert(h, 1); print(h)
deque([1, 100, 150], maxlen=3)

>>> insert(h, 100); print(h)
deque([1, 100, 100], maxlen=3)

>>> insert(h, 20); print(h)
deque([1, 20, 100], maxlen=3)

Answer 5

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.

Answer 6

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.

Answer 7

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.