Heapq

Python’s heapq module implements a min-heap using a regular list. The smallest element is always stored at index 0. The structure of the heap is a binary tree and the parent node is always smaller than the child node.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

import heapq

class element:
    score: int

    def __lt__(self, other):
        if not isinstance(other, element):
            return NotImplemented

        return self.score < other.score

def do_something():
    list: list[element] = []

    ...

    heapq.heappush(list, new_element)

    heapq.heappushpop(list, new_element)

• 17: heappush(heap, item) inserts a new item while preserving the heap property.
• 19: heappushpop(heap, item) first inserts the item and then removes and returns the smallest element. It is usually more efficient than calling heappush() followed by heappop() separately.