Heaps and priority queues

A complete tree that secretly lives in a flat array - giving you the smallest item on demand, and the arithmetic that makes pointers unnecessary.

Every scheduler, every shortest-path finder, every "give me the top 10" query has the same nagging need: repeatedly pull the smallest (or largest) thing out of a changing pile - fast. A sorted list makes that pull cheap but every insert expensive. A binary heap strikes the perfect bargain: $O(\log n)$ to add, $O(\log n)$ to remove the minimum, and $O(1)$ to peek at it - all inside a plain flat array with no pointers at all.

A complete tree that hides in an array

Because the tree is complete, we never need pointers to wire nodes together. Just write the tree out level by level into an array, and the structure is encoded purely by index arithmetic. For the node stored at index $i$:

That is the whole trick. "Go to my child" is a multiply-and-add; "go to my parent" is a subtract-and-halve. No allocation, no dereferencing - the array is the tree, and cache-friendly to boot. The heap property ($\text{parent}\le \text{children}$) is only a partial order: siblings have no defined relationship, which is exactly why a heap is cheaper to maintain than a fully sorted array.

See it: tree and array, sift up and sift down

Insert a value and watch it drop into the next free array slot, then sift up - swapping with its parent while it is smaller - in the tree and the array at once. Extract-min removes the root, drops the last element into its place, and sifts down. Click any node or cell to reveal its live $2i+1$ / $2i+2$ index math.

Insert and extract-min in code

The entire data structure is one array plus two helpers. Notice there is not a single pointer or node object - every "move" is index arithmetic.

class MinHeap:
    def __init__(self):
        self.a = []                          # the backing array

    def push(self, x):
        self.a.append(x)                     # land in the next free slot
        self._sift_up(len(self.a) - 1)

    def pop_min(self):
        top = self.a[0]                     # the minimum - O(1) to read
        last = self.a.pop()
        if self.a:
            self.a[0] = last                # move last element to the root
            self._sift_down(0)
        return top

    def _sift_up(self, i):
        while i > 0:
            parent = (i - 1) // 2            # parent index
            if self.a[i] >= self.a[parent]:
                break                        # heap property holds
            self.a[i], self.a[parent] = self.a[parent], self.a[i]
            i = parent

    def _sift_down(self, i):
        n = len(self.a)
        while True:
            l, r, small = 2*i + 1, 2*i + 2, i   # children indices
            if l < n and self.a[l] < self.a[small]: small = l
            if r < n and self.a[r] < self.a[small]: small = r
            if small == i:
                break
            self.a[i], self.a[small] = self.a[small], self.a[i]
            i = small

In real Python you would just reach for the standard library - import heapq gives you heappush and heappop over an ordinary list, implementing exactly this. Building it once by hand is what makes that black box transparent.

Check yourself