Chapter 7 — Heaps & Priority Queues
Source:
src/main/kotlin/heap/Master idea: a heap is a lazy sorted structure — it answers “what’s the smallest/largest?” in $O(\log n)$ without keeping the whole collection sorted. Nearly every heap problem is one of three moves: keep the top k, split into two halves, or process in priority order.
Prerequisites: arrays, the BFS/level ideas from Chapter 5, and a willingness to read “sort, but only enough” as the answer.
Problems at a glance (this chapter’s core set)
| # | Problem | Pattern | Complexity | Page |
|---|---|---|---|---|
| 7.1 | Top K Frequent Elements | min-heap of size k | $O(n \log k)$ | → |
| 7.2 | Find Median From Data Stream | two heaps (max + min) | $O(\log n)$ / add | → |
| 7.3 | Sliding Window Median | dual heap + lazy deletion | $O(n \log k)$ | → |
| 7.4 | Trapping Rain Water II | min-heap boundary expansion | $O(mn \log(mn))$ | → |
| 7.5 | IPO (Maximize Capital) | greedy + max-profit heap | $O((n+k) \log n)$ | → |
| 7.6 | Meeting Rooms III | busy/available heaps | $O(m \log n)$ | → |
| 7.7 | Single Threaded CPU | event + ready queues | $O(n \log n)$ | → |
| 7.8 | The Skyline Problem | sweep line + height multiset | $O(n log n)$ | → | | 7.9 | Design Hit Counter | FIFO queue with expiry pop | $O(1)$ amortized | → | | 7.10 | Longest Happy String | max-heap with 2-cap | $O(n)$ | → | | 7.11 | Merge K Sorted Lists | k-way heap merge | $O(n log k)$ | → | | 7.12 | Find Score After Marking | min-heap lazy skip | $O(n log n)$ | → | | 7.13 | Finding MK Average | three-bucket heaps | $O(log m)$ | → |
The rest of the heap/ directory
src/main/kotlin/heap/ also holds: DualBalancedHeap.kt (an alternate sliding-window median), FindingMKAverage.kt (three-heap window stats), FindKClosestElements.kt, FindScoreOfAnArrayAfterMarkingAllElements.kt, LongestHappyString.kt (greedy with a max-heap of character counts), and MedianFromRunningStream.kt variants. The general-purpose heap lives in src/main/kotlin/ too — sliding_window/, quicksort/, and greedy/ all import the same PriorityQueue idiom.
New pages are appended to the table above as they’re written.