AI InterviewSearch…Search problems, topics, or pages…Ctrl KGet started

Topic

Heap coding problems

A heap (priority queue) hands back the smallest — or largest — element in logarithmic time while new ones keep arriving.

New to heap? Read the Heaps and Priority Queues tutorial first.

106 problems · 8 easy · 63 medium · 35 hard · judged by hidden tests in 13 languages

106problems

8 easy

63 medium

35 hard

Sign in to tick off what you solve.

Study plan: 14 problems · about 8 h 10 min

Start the study plan

Next up: Last Stone Weight

How it works

Heap, step by step

Keeping the minimum on top, with a binary heap

heap = [2, 5, 3, 7, 9, 6, 8]; push(4); pop()

2537968array20513273946586children of i: 2i + 1 and 2i + 2

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.

0:01 / 0:27Step 1 of 7
Transcript · 7 steps

Study plan

Learn heap in 8 days

14 of the 106 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 92 in the full list below are practice at your own pace. Then move on to Ordered Set.

  1. Day 1

    about 1 h 15 min

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

  2. Day 2

    about 55 min

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

  3. Day 3

    about 1 h 10 min

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

  4. Day 4

    about 1 h 10 min

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

  5. Day 5

    about 1 h 10 min

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

  6. Day 6

    about 50 min

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

  7. Day 7

    about 50 min

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

  8. Day 8

    about 50 min

    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 Coding Problems: 106 Questions with Solutions

106 heap coding problems — 8 easy · 63 medium · 35 hard — with solutions in 13 languages. Plus a step-by-step walkthrough and a 8-day plan.

  • Problems: 106
  • By difficulty: 8 easy · 63 medium · 35 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.

New to heap? Read the Heaps and Priority Queues tutorial first.

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 106 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 92 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 (8)

Medium (63)

Hard (35)

Companies that ask heap problems

Next topic: Ordered Set