Pattern #28

Heap / Priority Queue

Important interview questions, thinking patterns, Min/Max Heap invariants, Top K size algorithms, two-heaps median finding, and container/heap rules in Go.

Must Solve

15 core questions — solve these first.

  1. 1.Kth Largest Element in an Array
    medium
  2. 2.Top K Frequent Elements
    medium
  3. 3.K Closest Points to Origin
    medium
  4. 4.Find Median from Data Stream
    hard
  5. 5.Merge K Sorted Lists
    hard
  6. 6.Task Scheduler
    medium
  7. 7.Last Stone Weight
    easy
  8. 8.Kth Largest Element in a Stream
    easy
  9. 9.Meeting Rooms II
    medium
  10. 10.Reorganize String
    medium
  11. 11.Furthest Building You Can Reach
    medium
  12. 12.Smallest Range Covering Elements from K Lists
    hard
  13. 13.IPO
    hard
  14. 14.Minimum Cost to Connect Sticks
    medium
  15. 15.Total Cost to Hire K Workers
    hard

Also Important

10 more questions worth practicing.

  1. 16.Kth Smallest Element in a Sorted Matrix
    medium
  2. 17.Find K Pairs with Smallest Sums
    medium
  3. 18.Seat Reservation Manager
    medium
  4. 19.Single-Threaded CPU
    medium
  5. 20.Process Tasks Using Servers
    medium
  6. 21.Maximum Performance of a Team
    hard
  7. 22.Minimum Number of Refueling Stops
    hard
  8. 23.Ugly Number II
    medium
  9. 24.Sliding Window Median
    hard
  10. 25.Minimum Cost to Hire K Workers
    hard

How to Think

  1. Need smallest item again and again?Min Heap (Peek O(1), Pop O(log N))
  2. Need largest item again and again?Max Heap (Peek O(1), Pop O(log N))
  3. Need Top K largest items?Min Heap of size K (O(N log K) time)
  4. Need Kth largest item?Min Heap of size K (Top is the answer!)
  5. Need merge K sorted lists?Min Heap storing candidate head nodes
  6. Need process highest-priority task?Priority Queue (stores (priority, payload))

Go container/heap Interface

Standard Min Heap Implementation in Go

import "container/heap"

type IntHeap []int

func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] } // Min Heap (change to > for Max Heap!)
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *IntHeap) Push(x interface{}) {
    *h = append(*h, x.(int))
}

func (h *IntHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

// Usage:
// h := &IntHeap{}
// heap.Init(h)
// heap.Push(h, 5)
// minVal := heap.Pop(h).(int)

👉 Push/Pop: O(log N) | Peek Top: h[0] in O(1) | Init: O(N)

Why Min Heap for K Largest? (Crucial Interview Concept)

To find the K largest values in an array of size N, maintain a Min Heap of size K.

Why Min Heap? Because among the K largest items kept, the smallest element stays at the root (top). When a new element comes along:

heap.Push(h, val)
if h.Len() > K {
    heap.Pop(h) // Evicts the smallest element among the top K candidates!
}

👉 After processing all N items, the top of the Min Heap is the Kth largest element in O(N log K) time!

Two Heaps Median Pattern

Max Heap (Lower Half)

Stores the smaller half of data numbers. Root yields the maximum element of the lower half.

Min Heap (Upper Half)

Stores the larger half of data numbers. Root yields the minimum element of the upper half.

Visual Memory Rule
Peek Top    → O(1) time
Push / Pop  → O(log N) time
Top K       → Heap size K (O(N log K) time)
Kth Largest → Min Heap size K (Root = answer)
Kth Smallest→ Max Heap size K (Root = answer)

💡 Golden Rule: "If you repeatedly need 'the best next item,' think Heap / Priority Queue."

Common Interview Mistakes

1. Thinking Heap Array is Sorted

Assuming heap[1] is the 2nd smallest element. A heap is NOT globally sorted — only parent vs child order is guaranteed!

2. Using Max Heap for Kth Largest

Using Max Heap requires storing all N elements (O(N log N)). Use a Min Heap of size K (O(N log K)) instead!

3. Forgetting to Evict When Size > K

Pushing into the heap without calling heap.Pop() when len > K allows the heap size to grow to N.

4. Inverting Go Less() Comparator

Accidentally writing h[i] > h[j] when you intended a Min Heap makes it a Max Heap instead. Double-check comparator direction!

Interview Rules

  1. 1. Repeated minimum? → Min Heap (Peek O(1), Pop O(log N))
  2. 2. Repeated maximum? → Max Heap
  3. 3. Top K largest? → Min Heap of size K (O(N log K) time)
  4. 4. Top K smallest? → Max Heap of size K
  5. 5. Kth largest? → Min Heap top element
  6. 6. Merge K sorted lists? → Min Heap candidate from each list (O(N log K))
  7. 7. Median stream? → Two Heaps: Max Heap (lower half) + Min Heap (upper half)
  8. 8. Priority scheduling? → Priority Queue storing tuples (priority, task)

Small Rules

  1. Rule 1: Heap is NOT fully sorted — only the root is guaranteed minimum or maximum.
  2. Rule 2: For Top K problems, bound heap size to K to save memory and reduce time to O(N log K).
  3. Rule 3: Priority Queue items are tuples: (priority_value, payload).
  4. Rule 4: In algorithms like Dijkstra, handle stale entries by checking visited states upon popping.
  5. Rule 5: Build Heap (heapify) on an existing array takes O(N) linear time.

Production Thinking

Job Scheduling → Process Critical/High/Normal priority worker queues using Priority Queue

Server Load Balancing → Min Heap (current_load, server_id) to pick least busy server in O(1)

Delayed Tasks & Timers → Min Heap by scheduled execution time (scheduled_timestamp, task)

Streaming Top Products Analytics → Min Heap size 100 for top product sales across continuous multi-terabyte stream

Remember This

Need smallest repeatedly → Min Heap
Need largest repeatedly  → Max Heap
Top K largest            → Min Heap size K
Top K smallest           → Max Heap size K
Kth largest              → Min Heap top
Merge K sorted           → Min Heap
Median stream            → Max Heap + Min Heap
Insert                   → Bubble Up
Remove top               → Bubble Down

💡 Golden Rule: "If you repeatedly need 'the best next item,' think Heap / Priority Queue."