Skip to content

Heaps & Priority Queues

Lesson 4 of 7 in Recursion, Trees & Graphs · 35 min · Intermediate

Always hand me the smallest (or largest) next.

Introduction

An emergency room has 40 people waiting, and new patients keep arriving. How can the nurse always call the most urgent one next, without re-sorting the whole waiting room every time?

First come, first served is the wrong rule here: a sprained ankle can't go ahead of a heart attack just because it arrived earlier. Sorting the whole list after every arrival works, but it redoes almost all of its work each time. (Give every patient a number, with 1 the most urgent, so the nurse wants the smallest number.)

Look at what the nurse really needs. Not a fully ordered list, just the most urgent patient right now, and then again after that patient leaves.

Lesson overview

This lesson will show you how to:

  • Explain why a heap always keeps its smallest item at the root.
  • Find a node's children in a min-heap stored as a flat array.
  • Trace push by sifting a new value up until its parent is smaller.
  • Trace pop by moving the last item to the root and sifting it down.
  • Use a size-k min-heap to track the k-th largest value in a stream.
  • Explain why heapifying n unordered numbers costs O(n), not O(n log n).

The picture

Min-heap as a tree
2368459smallest is always the rootparent ≤ both childrenBinary tree with 7 nodes. Root 2. 2's children 4 and 3; 4's children 9 and 5; 3's children 8 and 6. Marked: 2 found.
The same heap as an array: children of i are 2i+1 and 2i+2
heap20413293548566its children: cells 3 and 4Array heap with 7 slots: 2, 4, 3, 9, 5, 8, 6. Marked: index 0 found.

Mental model

Picture a company where every boss is better than their direct reports, and "better" means a smaller number. The CEO is therefore the best of everyone, and you find them at the top without looking. A new hire starts at the bottom and swaps upward past any boss they beat; when the CEO leaves, the newest hire takes the empty seat and sinks until the order is right again.

A heap is only partly sorted: every parent is no bigger than its children, so the smallest sits at the root, and repairing one change costs a walk along one path, about log₂ n steps.

Words to know

min-heap
A heap whose root is the smallest value: every parent is less than or equal to its children. Python's heapq and Java's PriorityQueue are min-heaps by default.
max-heap
The mirror image: every parent is greater than or equal to its children, so the largest value is the root. C++'s priority_queue is a max-heap by default; pass std::greater to get a min-heap.
heap property
The one rule: no parent is bigger than its children (in a min-heap). It says nothing about siblings, so a heap is not sorted.
complete tree
A binary tree with every level full except maybe the last, which fills from the left. That is why a heap fits in an array with no gaps: the parent of index i is (i − 1) / 2 rounded down, and its children are 2i + 1 and 2i + 2.
sift up
Repair a too-small value at the bottom by swapping it with its parent until the parent is not bigger. Push does this.
sift down
Repair a too-big value near the top by swapping it with its smaller child until neither child is smaller. Pop does this.
heapify
Turn a whole unordered array into a heap in place, by sifting down every parent from the last one back to the root. It costs O(n), cheaper than n pushes at O(n log n). Some books also use the word for a single sift; here those are sift up and sift down.
priority queue
The idea: add items, and always remove the one with the best priority. A binary heap is the usual way to build one. Python has heapq, Java has PriorityQueue and C++ has priority_queue.

Watch it run

Step with → or Next. When a question pops up, make your guess. Try your own input once the guided run ends.

Getting the demo ready…

Recognise it

Most of the skill is noticing the clue in the problem statement.

Reach for it when

  • Yes: You keep needing the smallest or largest item of a collection that keeps changing.
  • Yes: The statement says "top K", "k-th largest" or "k-th smallest", "k closest" or "k most frequent".
  • Yes: Items arrive over time and you must answer after each arrival, like a running k-th largest or a running median.
  • Yes: You must always process the most urgent, cheapest or earliest item next: a scheduler, or merging k sorted lists.

Not this when

  • No: You need everything in sorted order once. Just sort: O(n log n), and simpler.
  • No: You need to search for a particular value, the next larger value or a range. A heap only knows its root, so use a binary search tree or a hash map.
  • No: Items must leave in the order they arrived (first in, first out). That is a plain queue, with no priorities.

Which pattern fits?

  1. Which pattern? 1 of 5

    Numbers arrive one at a time. After each arrival, report the 3rd largest number seen so far.

  2. Which pattern? 2 of 5

    Given an array of n numbers, print all of them in ascending order, once.

  3. Which pattern? 3 of 5

    Numbers are added to a set over time. For each query x, report the smallest number in the set that is larger than x.

  4. Which pattern? 4 of 5

    A shop serves customers strictly in the order they arrive: new people join the back, the next person is served from the front.

  5. Which pattern? 5 of 5

    You are given k sorted linked lists. Merge them into one sorted list.

The code

First the idea in plain steps. Then the same idea as real code, line for line.

Pseudocode
  1. push(x):
  2. append x at the end of the array
  3. while x has a parent that is bigger than x:
  4. swap x with its parent
  5. pop_many(heap, pops):
  6. 1popped = an empty list
  7. repeat pops times:
  8. 2smallest = heap[0]
  9. 3move the last element to heap[0] and shrink the heap
  10. i = 0; while i has a child:
  11. 4c = the smaller child of i
  12. 5if heap[c] >= heap[i]: stop
  13. 6swap heap[i] and heap[c]; i = c
  14. 7the moving value is in its place
  15. add smallest to popped
  16. 8return popped

The faint numbers are the rules in the Rule Rail under the stage. Same numbers, same order.

Getting the replay ready…

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


def pop(heap):
    smallest = heap[0]
    last = heap.pop()
    if heap:
        heap[0] = last
        sift_down(heap, 0)
    return smallest


def pop_many(heap, pops):
    popped = []
    for _ in range(pops):
        popped.append(pop(heap))
    return popped
Time · O(log n) per push or pop, O(1) to peek at the bestSpace · O(n) for the heap, O(1) extra for each repair
  • Push and pop each walk one path between a leaf and the root. A complete tree of n nodes has about log₂ n levels, so each costs O(log n). Peeking is O(1): the best value is always heap[0].
  • Pop moves the LAST element to the root, not a child. That keeps the tree complete, so the array never has a hole. It then sinks, always swapping with the SMALLER child in a min-heap. The larger child could not sit above the smaller one. In a max-heap it is the larger child.
  • Building a heap from n numbers (heapify, or build-heap) takes O(n), not O(n log n): sift down every parent from the last one back to the root. Half the nodes are leaves and need no work, a quarter sink at most one level, and so on, and that sum stays proportional to n. Pushing n numbers one by one is O(n log n). Python: heapq.heapify. Java: new PriorityQueue<>(collection). C++: the priority_queue constructor that takes a range, or std::make_heap.
  • Library defaults differ. Python's heapq and Java's PriorityQueue are MIN-heaps. C++'s priority_queue is a MAX-heap: write priority_queue<int, vector<int>, greater<int>> for a min-heap, as the code does. For a max-heap in Python, store negated values.
  • Top K needs the opposite heap to what you might guess: for the K largest, keep a MIN-heap of size K, so the weakest of the group is on top, ready to be evicted. For the K smallest, keep a max-heap of size K. The k-th largest example below uses the library; its picture is drawn with the push and pop shown above, so a real heapq can order equal-level nodes a little differently while the root is always the same.
  • A heap is not sorted and not stable. Do not loop over a heap's array and expect order; pop to get order. Equal priorities can come out in any order. Finding or removing an arbitrary item is O(n), and heapq in Python compares tuples element by element, so store (priority, item) pairs.

Worked examples

Real interview problems, solved with the same recipe.

Open on LeetCode (opens in a new tab)

Given an integer array nums and an integer k, return the kth largest element in the array. It is the kth largest in sorted order, not the kth distinct value.

Input

nums = [3,2,3,1,2,4,5,5,6], k = 4

Output

4

Approach

  1. Sorting works in O(n log n), but you only want one number. Keep just the k largest values seen so far.
  2. Use a MIN-heap that holds at most k numbers. Its root is the smallest of the k largest, which is exactly the kth largest.
  3. Push every number. The moment the heap holds k + 1, pop the smallest: it cannot be one of the k largest.
  4. Here the heap ends holding 4, 5, 5 and 6, so its root, 4, is the answer.
import heapq


def kth_largest(nums, k):
    heap = []
    for num in nums:
        heapq.heappush(heap, num)
        if len(heap) > k:
            heapq.heappop(heap)
    return heap[0]
Time · O(n log k)Space · O(k)

Knowledge check

Test yourself first. Try to answer these in your own words, then take the quiz below to check.

  1. In a min-heap stored in an array, where are the children of the value at index 3?
  2. Why does pop move the last element to the root, instead of promoting one of the root's children?
  3. In a min-heap, the moving value 6 sits above children 4 and 9. What happens during sift down?
  4. You have n unordered numbers and want a min-heap. What does build-heap (heapify) cost, and why?
  5. You want the 10 smallest numbers of a stream of a million. Which heap do you keep?

Question 1 of 5

In a min-heap stored in an array, where are the children of the value at index 3?

Assignment

Pick one, try it cold for ten minutes, then come back for the hint.

0 of 8 solved

  1. Solve Top K Frequent Elements (opens in a new tab) (LeetCode, medium)

    Hint: Count with a map first. Then you need the k biggest counts, which is a min-heap of size k over (count, value) pairs.

  2. Solve K Closest Points to Origin (opens in a new tab) (LeetCode, medium)

    Hint: Compare squared distances, so no square root is needed. Which kind of heap, and how big, keeps the k closest?

  3. Solve Merge k Sorted Lists (opens in a new tab) (LeetCode, hard)

    Hint: Only the front of each list can be the next output. Keep those k fronts in a min-heap and refill from the list you just took from.

  4. Solve Find Median from Data Stream (opens in a new tab) (LeetCode, hard)

    Hint: Split the numbers into a smaller half and a larger half using two heaps. Keep their sizes balanced and the median sits at the tops.

  5. Solve Task Scheduler (opens in a new tab) (LeetCode, medium)

    Hint: Always run the task with the most copies left. A max-heap finds it, but a task that just ran must wait out its cooldown before it can return.

  6. Solve Reorganize String (opens in a new tab) (LeetCode, medium)

    Hint: Place the most frequent remaining letter that is not the one you just placed. Hold the last letter aside for a turn.

  7. Solve Kth Smallest Element in a Sorted Matrix (opens in a new tab) (LeetCode, medium)

    Hint: Every row is already sorted, so it is like merging lists. Seed a min-heap with each row's first cell and pop k times.

  8. Solve IPO (opens in a new tab) (LeetCode, hard)

    Hint: Sort projects by the capital they need. Each round, move every project you can now afford into a max-heap of profits and take the best.

Additional resources