Skip to content

Topic 11 of 20

Heaps / Priority Queue

Always know the smallest or largest item in O(1): top-K, k-way merge, scheduling and running medians.

20 problems4 Easy12 Medium4 Hard

The concept

A heap (priority queue) is a complete binary tree stored in an array, where every parent is smaller than its children (a min-heap) or larger (a max-heap). You can read the top element in O(1) and push or pop in O(log n). Whenever a problem keeps asking "what is the smallest/largest/most urgent item right now?", a heap is the tool.

Four patterns cover almost every interview question. Top-K: keep a heap of size k, so finding the k largest of n items costs O(n log k) instead of a full sort. K-way merge: push the head of each sorted list and repeatedly pop the minimum. Two heaps: a max-heap for the lower half and a min-heap for the upper half give a running median. Greedy scheduling: sort by one attribute and use a heap to pick the best available option by another.

Know your language's heap API cold (heapq in Python, PriorityQueue in Java, priority_queue in C++), including how to build a max-heap and how to push tuples with a tie-breaker.

Patterns you will learn

Problems, in order

  1. 1

    The basic size-k min-heap for a stream.

    Top-K with a Size-K HeapReported at: GoogleAmazonMeta+2
  2. 2

    Straightforward max-heap simulation.

    Max-Heap SimulationReported at: AmazonVisaNvidia+1
  3. 3

    Repeatedly process the current maximum.

  4. 4

    Ranking with a heap or a sort; a quick API drill.

    Heap / SortingReported at: Google
  5. 5

    Heap vs quickselect trade-offs; asked everywhere.

    Top-K / QuickselectReported at: MetaAmazonMicrosoft+6
  6. 6

    Top-K by a custom key; a Meta and Amazon staple.

    Top-K with a Size-K HeapReported at: MetaAmazonMicrosoft+2
  7. 7

    Top-K with tie-breaking comparators.

    Top-K with Custom OrderingReported at: AmazonMicrosoftGoogle+4
  8. 8

    Greedy counting or heap simulation with cooldowns.

    Greedy Scheduling with a HeapReported at: AmazonMetaMicrosoft+1
  9. 9

    Always place the most frequent remaining character.

    Greedy with a Max-HeapReported at: AmazonMetaGoogle+2
  10. 10

    A max-heap with run-length constraints.

  11. 11

    A feed design using k-way merge of timelines.

    K-way MergeReported at: GoogleAmazonWalmart Global Tech
  12. 12

    Lazy frontier expansion from sorted arrays.

    K-way MergeReported at: AppleAmazonLinkedIn+1
  13. 13

    Generating an ordered sequence without duplicates.

    Heap / Multiple PointersReported at: Microsoft
  14. 14

    Event simulation with sorted arrivals and a heap.

  15. 15

    Save ladders for the biggest climbs using a heap.

    Greedy with a Min-HeapReported at: AmazonGoogleMicrosoft
  16. 16

    Fix the minimum by sorting and keep the best k sums in a heap.

  17. 17

    The canonical two-heap running-median problem.

  18. 18

    Two heaps with lazy deletion inside a window.

    Two Heaps + Lazy DeletionReported at: MetaMicrosoftSpotify
  19. 19
    IPOHard

    Unlock projects by capital, then pick by profit.

    Sort + Heap (Greedy)Reported at: Uber
  20. 20

    K-way merge while tracking the current range.