Learn · DSA · Pattern 8
Heaps & Greedy
A heap keeps the most important item always ready at the top — so you can grab the biggest (or smallest) again and again, fast. It’s the tool behind “top 10”, schedulers, and shortest-path.
Before we start
- What a heap / priority queue is
- Why the top is always the min (or max), fetched in O(log n)
- The “top-K / Kth largest” pattern
- What “greedy” means and when it works
- Solve top-K and Kth-largest problems
- Pick a heap when you keep needing “the next most/least”
- Explain a heap vs sorting the whole list
Why you’re learning it: “find the top K” shows up constantly, and a heap is the clean O(n log k) answer where sorting everything is wasteful. ⏱️ ~30 min.
The idea
Think of a hospital ER triage. Patients don’t get seen in arrival order — the most urgent is always next, no matter when they walked in. A heap (a.k.a. priority queue) does exactly this: it always keeps the min (or max) at the top, hands it to you in one step, and re-settles itself in O(log n).
A min-heap: the smallest (1) sits on top, and every parent is smaller than its children. Grab the top, and the heap rebalances.
When to reach for it
Why not just sort? Sorting everything to grab the top 10 is O(n log n) and wasteful. A heap of size K does it in O(n log k) — and works even on an endless stream where you can’t sort.
Greedy — the cousin idea
A greedy algorithm grabs the locally best choice at each step and never looks back. Sometimes that gives the global best (making change, scheduling, Dijkstra’s shortest path — which uses a heap). Sometimes it doesn’t — knowing when greedy is safe is the skill.
Where you’ll use it — real life
The OS and job queues run the highest-priority task next — a priority queue.
Dijkstra’s algorithm (maps, routing) pulls the nearest unvisited node from a heap each step.
Top 10 most-viewed, most-active users, biggest transactions — heap of size K.
A priority column on the Relay job queue (your portfolio ladder) is a heap in action.
Now YOU do the reps
Out loud: “Why use a heap instead of sorting the whole list to find the top K?” Then log it in your Journal.
🎉 That’s the whole DSA spine. Back to your Siemens roadmap →