Heaps & Priority Queues

9 cards, about a minute. Read them the night before an interview, or right after the chapter to lock it in.

1. ◆what it is

   A heap is a complete binary tree in an array: every parent ≤ its children (min-heap). The min sits at index 0; children of i are 2i + 1 and 2i + 2.

   #1
2. O( )cost

   peek O(1) · offer/poll O(log n) · build from n values O(n) · remove(x)/contains O(n) · heap sort O(n log n) in O(1) space.

   #2
3. ↯use it when

   You need the current min/max while items keep arriving: top-k, k closest, running median, merge k sorted lists, greedy "take the best next".

   #3
4. { }template

   k largest: min-heap, pq.offer(x); if (pq.size() > k) pq.poll(); — the root is the k-th largest. k smallest: the same with a max-heap.

   #4
5. { }template

   Median: max-heap low + min-heap high. Offer to low, move low's max to high, move it back if high is bigger. Median = the tops.

   #5
6. { }template

   K-way merge: one cursor per sorted list in a min-heap. Poll the smallest, offer that list's next. O(N log k) time, O(k) space.

   #6
7. !trap

   Printing or iterating a PriorityQueue is NOT sorted — only repeated poll() returns values in order.

   #7
8. !trap

   (a, b) -> a - b overflows for far-apart values and silently mis-orders the heap. Use Integer.compare or Comparator.comparingInt.

   #8
9. ✦pro tip

   No decrease-key in Java: offer a new entry and skip stale ones when you poll them (lazy deletion), as Dijkstra does.

   #9

Shaky on a card? Open the chapter or flip its recall cards.