Heap / Priority Queue

Explore heap interview patterns with animated top-k, task scheduling and running median problems. Watch values swap up and down and study Python solutions.

The pattern

Heaps: the best item on top, in O(log n)

A heap (priority queue) keeps the smallest, or largest, item on top. Reading it is O(1), and adding an item or removing the top is O(log n). Use one whenever a problem keeps asking “what's the biggest (or smallest, or newest) right now?” while items come and go.

132745103122734455min on topindex 1 → 3, 4

1A tree stored in an array

A heap is a complete binary tree kept in a plain array: index i's children are at 2i + 1 and 2i + 2. In a min-heap every parent is ≤ its children, so the smallest value is always at index 0.

1327450push 0: it swaps past 2, then past 1

2Push swaps up, pop sinks down

Push: add at the end, then swap with the parent while it's smaller. Pop: take the top, move the last value to the top, then swap it with its smaller child until it fits. Both walk one path: O(log n).

531798lower half (max)upper half (min)5 | 7median = (5 + 7) / 2 = 6

3Keep only what you need

For the k largest, keep a min-heap of size k: its top is the weakest of them, the one to throw out. For a running median, two heaps face each other: a max-heap of the lower half and a min-heap of the upper half.

How to spot it

  • “kth largest”, “top k”, “k closest”: a heap of size k, ordered the opposite way, so the item to throw out is on top.
  • Repeatedly take the best item and put something back (stones, tasks): a heap of everything.
  • Merging sorted lists or “the newest across many lists”: a heap seeded with each list's head.
  • A running median: two heaps, one per half.

Reading the pictures

  • The tree and the row under it are the same heap. The small number under each array cell is its index.
  • Red marks the path a value just swapped along; teal is where it settled.
  • Python's heapq is a min-heap; for a max-heap, push negated values. To play with a heap yourself, see the Heap page.

NeetCode 150 · Heap / Priority Queue

All 7 problems

Pick a problem to see it solved step by step. They're in NeetCode's order, roughly easiest first.

Kth Largest Element in a Stream

Easy

Design a class that starts with k and a list nums. Each add(val) adds a number to the stream and returns the kth largest number seen so far.

NeetCode's video solution Try it on LeetCode
Input

k = 3, nums = [4, 5, 8, 2], adds = [3, 5, 10, 9, 4]

nums (the starting list)

4
5
8
2

add(val) calls

3
5
10
9
4

min-heap array (size ≤ k = 3)

(empty)

the min-heap: the smallest of the k largest sits on top

(empty tree)

variables

k
3
returned so far
–

Press Play or Step to watch the solution run.

Step 0 / 17
900 ms

Brute force vs the pattern

On this input:

Pattern: O(log k) per add
36 ops
Brute force
50 ops

On a bigger input (k = 5, 200 values, then 200 adds):

Pattern
2,716 ops
Brute force
80,400 ops

Keep every value in a sorted list and read position k − 1. Each add has to find its place and shift the values after it: O(n) per add, and the list keeps growing.

“ops” is an illustrative count of selected algorithm operations, with estimates for sorting. It excludes drawing and frame creation and is not a timing benchmark. The complexity describes the Python solution. On small inputs a brute-force search may find the answer sooner.

How it works: Kth Largest Element in a Stream

Step by step

  • Where the moved value ended
  • Path it swapped along
  • The top: kth largest

Press Start or Step: the step the animation is on lights up below.

  1. 1

    A min-heap of at most k values

    self.heap, self.k = nums, k; heapify(self.heap)
  2. 2

    Push the new value

    It swaps up while smaller than its parent.

    heappush(self.heap, val)
  3. 3

    Too many → pop the smallest

    while len(self.heap) > self.k: heappop(self.heap)
  4. 4

    The top is the kth largest

    return self.heap[0]

Only the k largest values ever matter. Keep exactly those in a min-heap: its top is the smallest of the k largest, which is the kth largest overall.

add(val): push it; if the heap now holds k + 1 values, pop the top (the smallest, which can't be in the top k any more). Then the top is the answer. Each add is O(log k), and the heap never grows past k.

Spot it in an interview

  • “kth largest” or “top k” over a stream: a min-heap of size k.
  • For the kth smallest, flip it: a max-heap of size k.
time O(log k) per addspace O(k)

The heap never holds more than k + 1 values, and push and pop walk one root-to-leaf path.

Credits

Learn more from NeetCode

The problem list and order come from the NeetCode 150 by NeetCode (neetcode.io). The solutions here follow the approaches NeetCode teaches in the linked videos; the animations, explanations and code were written for CodeQuest. If these help, NeetCode's videos and site are well worth your time.

Problem statements are summarised in our own words; the full versions are on LeetCode.