Heaps and Priority Queues

Why you need a heap

Picture a hospital emergency room. People arrive in random order, but the doctor doesn't see whoever came first; they see whoever is in the worst shape. New patients keep coming in. The triage nurse has to do two things quickly:

• add a new patient;
• say who's most urgent right now and send them to the doctor.

That's a priority queue. It's almost always implemented with a binary heap. A heap does both operations in O(log n) and lets you peek at the minimum in O(1).

Compare it with the alternatives:

Structure	Add	Extract min
Unsorted array	O(1)	O(n)
Sorted array	O(n)	O(1)
Heap	O(log n)	O(log n)

What a binary heap is

A heap is a nearly complete binary tree: every level is full except possibly the last, which fills from left to right. A min-heap follows one rule: a parent is never greater than its children. That's why the minimum always sits at the root.

Note that siblings have no order between them. In the example, 3 is to the left of 2, and that's fine. A heap isn't a sorted array; it only guarantees that smaller things are higher up.

A tree that lives in an array

A heap doesn't need pointers. Walk the tree level by level, left to right, and write the values down in a row. You get a plain array:

Memorize the index relationships (zero-based):

• left child: 2*i + 1
• right child: 2*i + 2
• parent: (i - 1) // 2

Check it against the diagram: the node at index 4 (value 4) has parent (4-1)//2 = 1, which is node 3. It checks out.

Insertion: sift up

1. Put the new element at the end of the array. That's the first free spot on the bottom level.
2. While it's smaller than its parent, swap them.

Say we insert 0. It lands at index 7 and is compared with 7, then 3, then 1. It swaps with each of them and ends up at the root. The tree's height is log n, so there are at most log n steps.

Extracting the minimum: sift down

1. Remember the root; that's your answer.
2. Move the last element of the array to the root and shrink the array by one.
3. While that element is larger than at least one of its children, swap it with the smaller child.

Again the path runs top to bottom along the tree's height, so this is O(log n) too.

Heaps in five languages

Language	What to use	Default
Python	heapq	min-heap
Java	PriorityQueue	min-heap
C++	priority_queue	max-heap
Go	container/heap	you need your own type implementing the interface
JavaScript	no built-in	write your own class

The top-K pattern: a heap of size k

Example problem: from a stream of words, keep the k longest.

You could sort everything in O(n log n), but there's a better way. Keep a min-heap of size k. Its root holds "the weakest of the best." Push each new word onto the heap, and if it now holds more than k elements, pop the root. At the end, the heap contains exactly the k longest words.

The idea sounds backwards: to find the largest, you use a min-heap. That's how you quickly kick out the weakest candidate.

import heapq

def top_k_longest(words, k):
    heap = []  # min-heap of (length, word) pairs
    for w in words:
        heapq.heappush(heap, (len(w), w))
        if len(heap) > k:
            heapq.heappop(heap)  # drop the shortest
    return [w for _, w in heap]

Complexity

• insert and extract: O(log n); peek at the minimum: O(1);
• top-K: O(n log k) time and O(k) memory. When k is much smaller than n, that's noticeably faster than sorting. Plus the pattern works on a stream, where you can't see all the data at once.

How it sounds in an interview

"I need to repeatedly pull the minimum out of a changing set, so I'll use a priority queue backed by a binary heap: insert and extract in O(log n). For the k largest, I keep a min-heap of size k: the root holds the worst of the current candidates, so it's easy to evict. That's O(n log k) time and O(k) memory overall."

Common mistakes

• Mixing up min and max. In C++ the default heap is a max-heap; in Python and Java it's a min-heap. To get a max-heap in Python, push -x.
• Using a max-heap for the top-K largest. Then you have to keep all n elements instead of k.
• Assuming the heap is sorted. Only a sequence of extractions comes out sorted, not a walk over the array.
• Comparing the incomparable. In Python, a tuple (priority, obj) blows up on equal priorities if the objects can't be compared. Add a counter in the middle: (priority, i, obj).
• Getting the indices wrong. With zero-based indexing, the children are at 2i+1 and 2i+2, not 2i and 2i+1.

Now you know how a heap works inside and how to use one in any language. Practice comes next, and the "heap of size k" trick will definitely come in handy there.