DevPath
Tracks

Heaps and Priority Queues

The binary heap: how an array stores a tree, why push and pop cost O(log n), why heapify is O(n), and the top-k pattern.

intermediate45 min#heap#priority-queue#heapify#top-k

Prerequisites: Arrays and Dynamic Arrays, Trees and Binary Search Trees

Why it matters

Whenever a program must repeatedly answer "what is the most urgent item right now?" while new items keep arriving, a heap is the answer. Task schedulers, event simulations, Dijkstra's shortest path, merging sorted streams, and "find the k largest" all rely on it. A sorted array finds the minimum fast but is slow to insert into; an unsorted array inserts fast but is slow to search. A heap makes both operations O(log n).

Intuition

Think of a tournament bracket where the winner sits at the top. The only promise is local: every parent beats (is smaller than, in a min-heap) its children. Siblings are not compared with each other, and there is no left-to-right order. That weak promise is cheap to maintain and still guarantees the overall best item is always at the root.

A priority queue is the abstract idea (insert items, remove the one with the highest priority). A binary heap is the standard way to build one.

How it works

A binary heap is a complete binary tree (every level full except possibly the last, which fills left to right) stored in a plain array with no pointers. For the node at index i:

  • parent is at (i - 1) // 2
  • children are at 2i + 1 and 2i + 2
 array: [1, 4, 2, 9, 8, 7]

 index tree:        values:
       0                1
      / \              / \
     1   2            4   2
    / \ /           / \ /
   3  4 5           9  8 7
149827
The heap [1, 4, 2, 9, 8, 7] drawn as the tree it represents (green is index 1, amber its children). Every parent is smaller than its children, but siblings (4 and 2, or 9 and 8) are in no particular order.
1
0
4
1
parent
2
2
9
3
left child
8
4
right child
7
5
The same heap as the array that is really stored. Index 1 (value 4) has its children at 2 * 1 + 1 = 3 and 2 * 1 + 2 = 4 (values 9 and 8), and going back, (3 - 1) // 2 = 1 and (4 - 1) // 2 = 1.

The min-heap invariant: every node is less than or equal to its children.

  • Push: append at the end (the next free slot of the complete tree), then sift up: while the new item is smaller than its parent, swap them. At most log n swaps.
149827
Min-heap [1, 4, 2, 9, 8, 7]. We push 0.
step 1 / 5

Push 0 into the heap with sift-up. Green is the item being moved, amber is the parent it is compared with. It climbs only along one root-to-leaf path.

  • Pop: take the root as the answer, move the last array item to the root, then sift down: swap with the smaller child until neither child is smaller. At most log n swaps.
0498172
Min-heap [0, 4, 1, 9, 8, 7, 2]. Pop returns the root, 0, so the root slot must be refilled.
step 1 / 4

Pop from the heap after the push above, with sift-down. Green is the moving item, amber marks the two children being compared.

  • Heapify (build from an unsorted array): run sift-down on every non-leaf node, from the last parent back to the root. This looks like O(n log n) but is O(n): half the nodes are leaves needing no work, a quarter can sink at most one level, an eighth two levels, and that series sums to a constant times n.
  • Max-heap: flip the comparisons. Python's heapq is a min-heap only; the usual trick is to store negated values. JavaScript has no built-in heap, so you write one as below.

Top-k largest. Keep a min-heap of size k. For each number, if the heap has fewer than k items, push it; otherwise, if the number beats the heap's minimum, pop and push. The root is the k-th largest so far, which is why you use a min-heap for the largest items. Time is O(n log k), space O(k), and it works on streams you cannot hold in memory.

OperationTimeNotes
Peek minO(1)Root of the array
PushO(log n)Sift up
Pop minO(log n)Sift down
Heapify from n itemsO(n)Not O(n log n)
Search for arbitrary itemO(n)No ordering between siblings
Top-k of n itemsO(n log k)Heap of size k

Code: a min-heap and top-k

import json
 
def show(*xs):
    print(*(json.dumps(x, separators=(',', ':')) for x in xs))
 
class MinHeap:
    def __init__(self, items=()):
        self.a = list(items)
        for i in range(len(self.a) // 2 - 1, -1, -1):  # heapify: O(n)
            self._sift_down(i)
 
    def __len__(self):
        return len(self.a)
 
    def push(self, x):
        self.a.append(x)
        self._sift_up(len(self.a) - 1)
 
    def pop(self):
        a = self.a
        top, last = a[0], a.pop()
        if a:
            a[0] = last
            self._sift_down(0)
        return top
 
    def _sift_up(self, i):
        a = self.a
        while i > 0:
            p = (i - 1) // 2
            if a[p] <= a[i]:
                break
            a[p], a[i] = a[i], a[p]
            i = p
 
    def _sift_down(self, i):
        a, n = self.a, len(self.a)
        while True:
            smallest = i
            for c in (2 * i + 1, 2 * i + 2):
                if c < n and a[c] < a[smallest]:
                    smallest = c
            if smallest == i:
                return
            a[i], a[smallest] = a[smallest], a[i]
            i = smallest
 
def top_k_largest(nums, k):
    h = MinHeap()
    for x in nums:
        if len(h) < k:
            h.push(x)
        elif x > h.a[0]:
            h.pop()
            h.push(x)
    return sorted(h.a, reverse=True)
 
h = MinHeap([9, 4, 7, 1, 8, 2])
show(h.a)
h.push(0)
show(h.a)
show([h.pop() for _ in range(len(h))])
show(top_k_largest([5, 1, 9, 3, 7, 8, 2, 6], 3))

Both versions print:

[1,4,2,9,8,7]
[0,4,1,9,8,7,2]
[0,1,2,4,7,8,9]
[9,8,7]

The first line is the heapified array (note it is not sorted, just heap-ordered). Pushing 0 sifts it all the way to the root. Draining the heap returns items in sorted order, which is exactly heap sort. The last line is the three largest of eight numbers.

Common pitfalls

  • Expecting sorted order: iterating over the heap array does not give sorted output. Only repeated pops do.
  • Using a max-heap for top-k largest: it forces you to hold all n items. A min-heap of size k is smaller and faster.
  • Off-by-one in index math: with a 0-based array the children are 2i + 1 and 2i + 2. With a 1-based array they are 2i and 2i + 1. Mixing the conventions corrupts the heap.
  • Updating priorities in place: a plain heap cannot find an item in O(log n). Either push a new entry and ignore stale ones when popped (the lazy approach used in Dijkstra) or maintain an index map.
  • Sorting when you only need the best few: sorting is O(n log n); a heap is O(n log k).

Practice

Kth largest element in an array easy

Hint

Which end of a size-k heap holds the answer?

Show solution

Maintain a min-heap of size k as in top_k_largest. After processing every number, the root is the k-th largest. O(n log k) time, O(k) space. (Quickselect gives O(n) average but is more intricate.)

Merge k sorted lists medium

Hint

You only ever need the smallest head among k lists.

Show solution

Push the first element of each list as a tuple of value, list index, and position. Pop the smallest, append it to the output, and push the next element from the same list if there is one. The heap never exceeds k items, so the total time is O(N log k) for N total elements.

Running median of a stream hard

Hint

Split the data into a lower half and an upper half, and keep the halves balanced in size.

Show solution

Keep a max-heap for the lower half and a min-heap for the upper half. Insert each new number into the appropriate heap, then rebalance so the sizes differ by at most 1. The median is the root of the larger heap, or the average of both roots when sizes are equal. Each insert is O(log n) and the median query is O(1).

Why is heapify O(n)? medium

Hint

Count how far each level of nodes can sink.

Show solution

About n/2 nodes are leaves (0 swaps), n/4 can sink 1 level, n/8 can sink 2, and so on. The total work is at most n times the sum of k divided by 2 to the power k, which converges to a constant. So the whole build is O(n). Pushing n items one by one would cost O(n log n).

Interview questions

  1. Why is a binary heap stored in an array? It is a complete tree, so index arithmetic replaces pointers, giving compact memory and good cache behavior.
  2. How do you get the k largest items out of n? A min-heap of size k, O(n log k).
  3. Heap versus balanced BST for a priority queue? A heap is simpler and faster in practice for min or max only. A BST also supports ordered iteration, arbitrary delete and predecessor queries.
  4. Is heap sort stable? In place? In place yes (with the array as the heap), stable no.
  5. How do you implement decrease-key? Track each item's index, change the key, and sift up. Or use the lazy-deletion approach.

Interviewers look for: choosing a min-heap for top-k largest, stating O(n log k), knowing heapify is O(n), and recognizing "repeatedly take the best" as a heap signal.

Quick check

You must report the 10 largest values from a stream of 100 million numbers using little memory. What do you keep?

Finished this lesson?

Further resources

Related lessons