DSA & Implementation · core
Heap / Priority Queue
Top-k, k-way merge, scheduling.
Mental model
A heap gives you the min or max in O(1) and re-balances in O(log n). Whenever a problem says "top k", "k-th largest", or "merge k sorted", a heap of size k is usually the answer — far cheaper than sorting everything.
How to study Heap / Priority Queue
Begin by restating the mental model in your own words, then connect it to a concrete system you have built or operated. Name the mechanism, the constraint it addresses, and the trade-off it introduces. Use VisuAlgo — Binary Heap to check details, but close the source before writing your explanation. Retrieval is the learning step; rereading is only preparation.
Next, compare Heap / Priority Queue with the neighboring concepts in its roadmap. Ask what changes in correctness, latency, resource use, operability, and failure recovery. Complete Kth largest element with a heap, Top K Frequent Elements, Kth Largest Element in an Array and preserve the command, input, output, and one failed attempt as evidence. Finish by explaining the idea without jargon to someone who has not studied the track.
Proof of understanding
- Explain the mechanism from first principles and identify the state it reads or changes.
- Give one situation where the concept is the right choice and one where it is not.
- Predict a realistic failure mode before running the drill, then compare the prediction with evidence.
- Connect the result to a roadmap or build artifact instead of treating the concept as isolated trivia.
Common mistakes
- Sorting the whole input when a size-k heap suffices
- Inverting heap polarity: top-k smallest wants a size-k max-heap (evict the largest), top-k largest wants a size-k min-heap
- Forgetting most languages give a min-heap by default
Learn from primary sources
- VisuAlgo — Binary Heap (doc)
Practice and explain it back
Kth largest element with a heap
Return the k-th largest element of an unsorted array using a heap, without fully sorting.
Expected evidence: findKthLargest([3,2,1,5,6,4], 2) -> 5
Open the interactive drill →Top K Frequent Elements
LeetCode #347 — Top K Frequent Elements. Solve on LeetCode, then implement here if you want it in your drill queue. https://leetcode.com/problems/top-k-frequent-elements/
Expected evidence: Pass all LeetCode test cases for this problem.
Open the interactive drill →Kth Largest Element in an Array
LeetCode #215 — Kth Largest Element in an Array. Solve on LeetCode, then implement here if you want it in your drill queue. https://leetcode.com/problems/kth-largest-element-in-an-array/
Expected evidence: Pass all LeetCode test cases for this problem.
Open the interactive drill →Task Scheduler
LeetCode #621 — Task Scheduler. Solve on LeetCode, then implement here if you want it in your drill queue. https://leetcode.com/problems/task-scheduler/
Expected evidence: Pass all LeetCode test cases for this problem.
Open the interactive drill →Review prompts
- A size-k heap is O(n log k) and sorting is O(n log n). When is sorting still the better choice?
Build evidence
Use a roadmap capstone to turn this concept into working evidence.
Prerequisites
Related concepts
None assigned yet.