Get started

Heap Coding Problems: 61 Questions with Solutions

61 heap coding problems — 6 easy · 39 medium · 16 hard — with solutions in 13 languages. Plus a step-by-step walkthrough and a 8-day plan.

  • Problems: 61
  • By difficulty: 6 easy · 39 medium · 16 hard
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
  • Cost: Free on every plan; sign in to run and submit

A heap (priority queue) hands back the smallest — or largest — element in logarithmic time while new ones keep arriving. The k largest elements, merging sorted streams, scheduling by earliest deadline and running medians are its home ground; these problems practise choosing the heap's key, keeping it bounded at k, and pairing two heaps when the question needs both ends.

How heap works, step by step

3465978array304162539475862popped2heap = [3, 4, 6, 5, 9, 7, 8]
Keeping the minimum on top, with a binary heap. Example: heap = [2, 5, 3, 7, 9, 6, 8]; push(4); pop()
  1. A min-heap keeps every parent no larger than its children, so the minimum is always at the root. It lives in a plain array: the children of index i sit at 2i + 1 and 2i + 2, and the tree is just a way of reading that array.
  2. push(4) puts 4 in the next free slot, index 7, so the tree stays complete. Its parent is index (7 − 1) / 2 = 3, holding 7, and 4 < 7 breaks the heap rule there.
  3. 4 and 7 swap, so 4 rises to index 3 and 7 drops to index 7. Its new parent 5 is still larger, so it keeps climbing.
  4. 4 and 5 swap, so 4 rises to index 1 and 5 drops to index 3. Its new parent 2 is smaller, so sift-up stops: the heap rule holds again after 2 swaps, at most one per level.
  5. pop() takes the minimum, 2, from the root. The last value, 7, moves into the root so the tree stays complete, but 7 is larger than its children 4 and 3, so it must sift down.
  6. 7 swaps with its smaller child, 3 (not 4), so 3 rises and 7 drops to index 2. Its new children are 6 and 8, and one is smaller, so it keeps sinking.
  7. 7 swaps with its smaller child, 6 (not 8), so 6 rises and 7 drops to index 5. Index 5 has no children inside the heap, so it stops and the minimum 3 is on top. Push and pop each walk one root-to-leaf path: O(log n), and reading the minimum is O(1).

Heap study plan

14 of the 61 Heap problems (4 easy, 7 medium and 3 hard) over 8 days, about 8 h 10 min in all — the pattern first, then easiest to hardest. After that, the other 47 in the full list below are practice at your own pace. Then move on to Ordered Set.

Day 1

Learn the pattern: read the essentials and step through the walkthrough above, then solve these 3.

Day 2

Medium problems: the same pattern with one twist each. Name the twist before you code.

Day 3

More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

Day 4

More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

Day 5

More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

Day 6

Hard problems: the pattern combined with a second idea. Give each a full attempt before reading the editorial.

Day 7

Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.

Day 8

Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.

Next topic: Ordered Set

Heap: the essentials

When to reach for it

"The k largest, smallest, closest or most frequent"; "repeatedly take the best remaining item" — the two heaviest stones, the cheapest next edge, the meeting that ends first; merging k sorted lists; the median of a stream. If the alternative is to sort, take one item, change the data and sort again, a heap does each round in O(log n).

The pattern

For the k largest, keep a min-heap of at most k items: push each new item and pop the smallest whenever the size passes k. The heap then holds the k largest, and its top is the k-th largest. For best-first processing, push candidates as they become available and pop the best. Check which end your library hands back: Python's heapq and Java's PriorityQueue give the smallest, C++'s priority_queue the largest.

import heapq

def kth_largest(nums, k):
    heap = []
    for x in nums:
        heapq.heappush(heap, x)
        if len(heap) > k:
            heapq.heappop(heap)     # drop the smallest
    return heap[0]

Cost

Push and pop are O(log size). A heap capped at k over n items costs O(n log k) time and O(k) space. Building a heap from a whole array at once (heapify) is O(n).

Common mistakes

  • Heaping all n items to read the top k: correct, but O(n log n) time and O(n) space.
  • Negating keys to get a max-heap and forgetting to negate them back.
  • Pushing tuples whose second element cannot be compared: Python compares it when the first ties, so add a counter in between.
  • Expecting the heap's array to be sorted; only its top is guaranteed.

Start with

All heap problems

Easy (6)

Medium (39)

Hard (16)

Companies that ask heap problems

Next topic: Ordered Set