Heaps and Priority Queues

A tree stored in an array where every parent is smaller (min-heap) than its children. Constant-time min and logarithmic push/pop.

Level: intermediate

What is it?

A binary heap is a complete binary tree stored in an array, where each parent is less than or equal to its children (min-heap) or greater than or equal (max-heap). The root is always the extreme element. For index i, the children are at 2i+1 and 2i+2 and the parent at (i-1)//2. Push adds at the end and sifts up; pop removes the root, moves the last element to the top, and sifts down. Both are O(log n).

Why does it matter?

Whenever you repeatedly need 'the next most urgent thing' — the shortest job, the closest node, the top-k values, the next timer — a heap does it in O(log n) without keeping everything sorted. It implements priority queues, Dijkstra's algorithm, and heap sort.

Mental model

A tournament bracket kept only at the top. You always know the champion instantly. When the champion leaves, you promote a replacement and let it sink to where it belongs; you never bother ranking the rest fully.

How it works

Shape property: a complete tree, so it packs into an array with no pointers.
Heap property: parent ≤ children (min-heap). Siblings are not ordered relative to each other.
peek is O(1); push and pop are O(log n) because they follow one root-to-leaf path.
Building a heap from n elements with heapify takes O(n), not O(n log n).
Python's heapq is a min-heap on a list; store negatives or tuples for max-heaps and priorities.
Top-k of a stream: keep a heap of size k and compare each new item with its root.

Steps

Push at the end of the array
Sift up while smaller than the parent
Pop takes the root
Move the last item to the root
Sift down while larger than a child

Code example: A priority queue with heapq

import heapq

tasks = []
heapq.heappush(tasks, (2, "write report"))
heapq.heappush(tasks, (1, "fix outage"))
heapq.heappush(tasks, (3, "lunch"))
print(heapq.heappop(tasks))    # (1, 'fix outage')  smallest priority first
print(tasks[0])                # (2, 'write report') peek at the next

Complexity and trade-offs

Time: Peek O(1); push and pop O(log n); heapify O(n)

Space: O(n)

Trade-offs

Fast access to the extreme element without full sorting
No efficient search for arbitrary items or ordered iteration
Priority updates need a decrease-key operation or lazy deletion

Real-world usage

Priority queues in schedulers and event simulations
Dijkstra's and Prim's algorithms
Top-k queries and running medians

Common mistakes

Expecting the heap's array to be sorted.
Using a max-heap where heapq only provides a min-heap.
Scanning the whole heap to find or remove an arbitrary item.

Interview questions

How do you find the k largest elements in a stream?

Keep a min-heap of size k. For each new item, if it is larger than the heap's root, replace the root with it. The heap always holds the k largest seen so far, at O(log k) per item.

Why is heapify O(n)?

Most nodes are near the bottom and sift only a few levels. Summing the work by level gives a geometric series bounded by O(n), even though a single sift can take O(log n).

Heap versus sorted array as a priority queue?

A sorted array gives O(1) min but O(n) insertion. A heap gives O(log n) for both push and pop, which wins when you interleave inserts and removals.