Heaps (priority queues)

Always know the smallest item, even while items keep arriving. Push and pop in O(log n), peek in O(1).

what

A complete binary tree stored in an array, where every parent is ≤ its children. The minimum sits at index 0.

use when

You repeatedly need the smallest (or largest) item while adding new ones: top-k, merging sorted lists, scheduling, Dijkstra.

time

O(log n) push and pop, O(1) peek

space

O(n)

You’ll recognise it when

You keep taking out the smallest (or largest) item while new items keep arriving.
The question asks for the top k, the k-th largest, or the k closest points.
You’re merging k sorted lists or streams and always need the smallest head.
Things happen in time or priority order: events, deadlines, retries, the next task a CPU should run.
You’re running Dijkstra’s or Prim’s algorithm and need the closest unvisited node next.

If all the data is there up front and nothing new arrives, sorting once is just as good. If you also need to delete arbitrary items or walk everything in order, reach for a balanced tree or sorted set instead.

The idea

Think of an office where every manager must be at least as senior as the people who report to them. Then the most senior person is always at the top, and you never need to rank everyone else. When someone new joins at the bottom, they swap with their manager until the rule holds again. When the boss leaves, the last person hired fills the empty chair and gets demoted past more senior people until the rule holds.

A heap is that org chart for numbers. In a min-heap, every parent is ≤ its children, so the smallest item is always at the root. Other items are only loosely ordered, and that looseness is what makes every change cheap: a push or pop only fixes one path from the root to a leaf, and that path is about log₂ n long.

The tree is never stored as nodes and pointers. It’s complete (every level full except the last, which fills left to right), so it fits in a plain array with no gaps:

	index
left child of `i`	`2i + 1`
right child of `i`	`2i + 2`
`parent` of `i`	`(i - 1) // 2`

How it works

The heap is an array a, with a[0] the minimum. Scroll through the steps and the graphic follows along: the tree on top and the array underneath are the same data, and the same item lights up in both. Press edit to try your own pushes and pops.

push(x): append x at the end of the array. The tree stays complete, but x might be smaller than its parent.
Sift up: look at the parent of index i, at (i - 1) // 2, and compare the two values.
If the parent is bigger, swap them and move i up to the parent’s index.
Stop as soon as the parent is ≤ x, or x reaches the root. Only that one path changed, so the rest of the heap is still valid.
pop(): the answer is a[0], the root. Take it.
Fill the hole with the last item of the array, so the tree stays complete. That item came from the bottom, so it’s probably too big for the top.
Sift down: look at the children of i and pick the smaller one as child.
If a[i] is bigger than that child, swap them and move i down.
Stop when a[i] is ≤ its smaller child, or i has no children. The heap is valid again.

loading heaps…

Why swap with the smaller child? After the swap, that child becomes the parent of its old sibling. Only the smaller of the two is ≤ the other, so only it keeps the rule true. Each swap fixes one parent-child pair without breaking any other, which is why a single path is enough.

class MinHeap:
    """A binary min-heap stored in a list: the children of a[i] are at
    2i + 1 and 2i + 2, and every parent is <= its children."""

    def __init__(self):
        self.a = []

    def size(self):
        return len(self.a)

    def peek(self):
        return self.a[0]                      # the smallest item is at the root

    def push(self, x):
        self.a.append(x)
        self._sift_up(len(self.a) - 1)

    def pop(self):
        a = self.a
        top = a[0]
        last = a.pop()                        # remove the last slot
        if a:
            a[0] = last
            self._sift_down(0)
        return top

    def _sift_up(self, i):
        a = self.a
        while i > 0:
            parent = (i - 1) // 2
            if a[parent] <= a[i]:
                break
            a[i], a[parent] = a[parent], a[i]
            i = parent

    def _sift_down(self, i):
        a = self.a
        n = len(a)
        while True:
            child = 2 * i + 1
            if child >= n:
                break
            if child + 1 < n and a[child + 1] < a[child]:
                child += 1                    # the right child is smaller
            if a[i] <= a[child]:
                break
            a[i], a[child] = a[child], a[i]
            i = child

#include <utility>
#include <vector>
using namespace std;

// A binary min-heap stored in a vector: the children of a[i] are at
// 2i + 1 and 2i + 2, and every parent is <= its children.
class MinHeap {
    vector<int> a;

    void siftUp(int i) {
        while (i > 0) {
            int parent = (i - 1) / 2;
            if (a[parent] <= a[i]) break;
            swap(a[i], a[parent]);
            i = parent;
        }
    }

    void siftDown(int i) {
        int n = a.size();
        while (true) {
            int child = 2 * i + 1;
            if (child >= n) break;
            if (child + 1 < n && a[child + 1] < a[child]) {
                child++;                              // the right child is smaller
            }
            if (a[i] <= a[child]) break;
            swap(a[i], a[child]);
            i = child;
        }
    }

public:
    int size() const { return a.size(); }

    int peek() const { return a[0]; }                 // the smallest item is at the root

    void push(int x) {
        a.push_back(x);
        siftUp(a.size() - 1);
    }

    int pop() {
        int top = a[0];
        int last = a.back();                          // remove the last slot
        a.pop_back();
        if (!a.empty()) {
            a[0] = last;
            siftDown(0);
        }
        return top;
    }
};

import java.util.ArrayList;

// A binary min-heap stored in a list: the children of a[i] are at
// 2i + 1 and 2i + 2, and every parent is <= its children.
class MinHeap {
    private final ArrayList<Integer> a = new ArrayList<>();

    int size() { return a.size(); }

    int peek() { return a.get(0); }                   // the smallest item is at the root

    void push(int x) {
        a.add(x);
        siftUp(a.size() - 1);
    }

    int pop() {
        int top = a.get(0);
        int last = a.remove(a.size() - 1);            // remove the last slot
        if (!a.isEmpty()) {
            a.set(0, last);
            siftDown(0);
        }
        return top;
    }

    private void siftUp(int i) {
        while (i > 0) {
            int parent = (i - 1) / 2;
            if (a.get(parent) <= a.get(i)) break;
            swap(i, parent);
            i = parent;
        }
    }

    private void siftDown(int i) {
        int n = a.size();
        while (true) {
            int child = 2 * i + 1;
            if (child >= n) break;
            if (child + 1 < n && a.get(child + 1) < a.get(child)) {
                child++;                              // the right child is smaller
            }
            if (a.get(i) <= a.get(child)) break;
            swap(i, child);
            i = child;
        }
    }

    private void swap(int i, int j) {
        int t = a.get(i);
        a.set(i, a.get(j));
        a.set(j, t);
    }
}

peek is just a[0]. The code has no library heap in it on purpose: in practice you’d use heapq, priority_queue or PriorityQueue (see Variations), but they do exactly this inside.

Why it’s O(log n)

A complete tree with n nodes has about log₂ n levels. Sift up climbs at most one level per swap, and sift down drops at most one level per swap, so push and pop each do at most log₂ n swaps. A heap of a million items needs at most 20.

Operation	Time
`peek`	O(1)
`push`, `pop`	O(log n)
build from n items with `heapify`	O(n)
n pushes one at a time	O(n log n)
find or delete an arbitrary item	O(n)

Heapify is O(n), not O(n log n). It sifts down every parent, from the last one back to the root. Half the nodes are leaves and never move, a quarter can move one level, an eighth two levels, and so on. That sum, n/4 · 1 + n/8 · 2 + n/16 · 3 + …, adds up to less than n.

Space is the array itself: O(n).

Common mistakes

Swapping with the left child every time

Sift-down must swap with the smaller child. If the right child is smaller and you swap with the left, the left child becomes the parent of something smaller than itself.

child = 2 * i + 1                                  # ✗ ignores the right child
if child + 1 < n and a[child + 1] < a[child]:
    child += 1                                     # ✓ pick the smaller one

Using the 1-based formulas on a 0-based array

Textbooks that start at index 1 use i // 2 for the parent and 2i, 2i + 1 for the children. With a 0-based array those land one slot off and quietly break the heap.

parent = i // 2          # ✗ 1-based formula
parent = (i - 1) // 2    # ✓ 0-based

Reading the array as if it were sorted

Only a[0] is special. a[1] is not necessarily the second smallest, and printing the list doesn’t give sorted order. To get the k smallest, pop k times (or use heapq.nsmallest).

Ties that compare the payload

With (priority, item) tuples, equal priorities make Python compare the items, which crashes for dicts and custom objects. Put a counter in between: it breaks ties and keeps equal priorities in insertion order.

heapq.heappush(h, (prio, job))              # ✗ TypeError on a tie
heapq.heappush(h, (prio, next(seq), job))   # ✓ seq = itertools.count()

Variations

Library heaps. Python’s heapq is a set of functions on a plain list and is always a min-heap. C++‘s std::priority_queue is a max-heap by default; use priority_queue<int, vector<int>, greater<int>> for a min-heap. Java’s PriorityQueue is a min-heap; pass Collections.reverseOrder() for a max-heap.
Max-heap by negation. With a min-heap only library, push -x and negate what you pop. For tuples, negate only the key you want reversed: (-priority, seq, item).
Top k with a size-k heap. To keep the k largest of a stream, use a min-heap and pop whenever it grows past k. Its root is the current k-th largest, and the whole pass is O(n log k).
Two heaps for a running median. A max-heap holds the lower half and a min-heap the upper half. Keep their sizes within one of each other; the median sits on top.
Lazy deletion. Binary heaps can’t cheaply delete or update an item in the middle. Push the new version instead, and skip stale entries when they reach the top. Dijkstra’s algorithm with a library heap works exactly like this.

Check yourself

5 quick questions. Pick an answer to see why it's right or wrong.

1
A job runner keeps accepting jobs, each with a run-at time. Every second it must start all jobs whose time has come, earliest first. New jobs can be scheduled earlier than ones already waiting. Which structure fits?
Jobs are due in time order, not arrival order, and new ones keep arriving, so you need “give me the earliest” with cheap inserts: O(log n) each with a heap. A FIFO breaks as soon as a later job is scheduled for an earlier time. Sorting once can’t absorb new jobs, and scanning a map is O(n) every tick.
2
What does this print?
```
import heapq
h = []
for x in [5, 4, 3, 2, 1]:
    heapq.heappush(h, x)
print(h)
```
A heap only promises that each parent is ≤ its children, so h[0] is the minimum and the rest is in heap order, not sorted order. Each push appends and sifts up: 4 swaps with 5, 3 swaps with 4, 2 climbs two levels, 1 climbs two levels. To read items in sorted order, pop them one by one.
3
What does this print?
```
import heapq
h = []
for x in [5, 1, 8, 3]:
    heapq.heappush(h, -x)
print(-heapq.heappop(h), -h[0])
```
heapq is always a min-heap. Pushing -x makes the largest value the smallest key, so the first pop gives -8, negated back to 8, and the new top is -5. Forgetting to negate on the way out is how you get -8 -5.

This sift_down has a bug. What does it print?

def sift_down(a, i):
    n = len(a)
    while 2 * i + 1 < n:
        child = 2 * i + 1
        if a[i] <= a[child]:
            break
        a[i], a[child] = a[child], a[i]
        i = child

a = [1, 5, 3, 9]      # a valid min-heap
a[0] = a.pop()        # pop the 1: move the last item to the root
sift_down(a, 0)
print(a[0], min(a))

5
You have all n numbers up front and want a heap of them. What does building it bottom-up (sift down each parent, from the last one back to index 0) cost?
Half the nodes are leaves and never move, a quarter move at most one level, an eighth at most two, and so on. That sum is less than n. Pushing the numbers one at a time is O(n log n), because each push can climb the full height; that’s the tempting wrong answer.