What Is a Heap?

The most important item, always on top

A priority queue lets you add items and always take out the most important one next. The usual way to build one is a heap.

Think of it like this: A hospital emergency room: patients aren't seen in arrival order but by how serious they are. Whoever is most urgent is always next.

The heap rule

A min-heap is a binary tree where every parent is smaller than or equal to its children. So the smallest item is always at the root. The tree is kept complete (filled row by row), so it can be stored in a plain list with no pointers:

heap = [1, 3, 2, 7, 4, 5]
#          1
#        /   \
#       3     2
#      / \   /
#     7   4 5
for i, value in enumerate(heap):
    kids = [heap[c] for c in (2 * i + 1, 2 * i + 2) if c < len(heap)]
    print(value, "-> children", kids)

Output

1 -> children [3, 2]
3 -> children [7, 4]
2 -> children [5]
7 -> children []
4 -> children []
5 -> children []

Adding and removing

• push: put the new item at the end, then swap it upward while it's smaller than its parent (“sift up”).
• pop: take the root, move the last item to the root, then swap it downward with its smaller child (“sift down”).

The tree has height log n, so both take O(log n). Looking at the smallest item is O(1).

*from the front, if you keep the list reversed – but adding is still O(n).