Heaps & Live Charts
Tunebox's live chart shows the most-played tracks right now, and plays arrive by the thousand every minute. Re-sorting after every play costs O(n log n) each time. A heap keeps the top item one step away and absorbs each change in O(log n) — it's the structure behind every "what matters most next?" question.
A complete binary tree, stored in a list
A heap is a binary tree with two rules. Shape: it's complete — every level is full except perhaps the last, which fills from the left. Order: in a min-heap, every parent is ≤ its children, so the smallest item is always at the root.
Because the shape has no gaps, the tree needs no nodes or pointers at all. Number the slots level by level and keep them in a plain list; parent and child links become arithmetic:
3 index: 0 1 2 3 4 5
/ \ heap: [3, 8, 5, 12, 9, 7]
8 5
/ \ / parent(i) = (i - 1) // 2
12 9 7 left(i) = 2 * i + 1
right(i) = 2 * i + 2heap = [3, 8, 5, 12, 9, 7]
i = 2
print(heap[(i - 1) // 2], heap[2 * i + 1])❓ Cross-question — "So a heap is just a sorted list?" No, and that's the point.
[3, 8, 5, 12, 9, 7]isn't sorted — 8 comes before 5. A heap only promises that each parent beats its own children. That weaker promise is much cheaper to keep, and it still puts the winner at index 0.
Sift-up: adding an item
Append the new item in the next free slot, which keeps the tree complete. Then swap it with its parent for as long as it's smaller. Each swap climbs one level, so a push is O(log n). Step through pushing a 1:
Sift-down: removing the top
To pop the minimum, move the last item into the root and shrink the list. Then push that item down, swapping it with its smaller child while that child is smaller than it. Pick the wrong child and a bigger value ends up on top:
Popping every item should give them back in sorted order, but this prints [1, 3, 5, 6, 2, 9], because sift_down only ever looks at the left child.
Popping everything off a heap is a sort — heapsort, O(n log n).
heapq: Python's min-heap
Python gives you sift-up and sift-down ready-made. heapq works on an ordinary list:
heapq is min-heap only. A chart wants the most plays on top, so push
negated counts — the smallest -plays is the biggest plays:
import heapq
charts = []
for plays in [40, 95, 12, 60]:
heapq.heappush(charts, -plays)
heapq.heappop(charts)
print(-charts[0])Heap items can be tuples, which compare element by element. (-plays, title)
ranks by plays and breaks ties alphabetically, without any extra code.
❓ Cross-question — "Why is
heapifyO(n), when n pushes cost O(n log n)?" It sifts down, starting from the last parent. Half the nodes are leaves and never move, a quarter move at most one level, an eighth at most two… That sum stays below 2n swaps.
Coming from Java/JS:
heapqis Java'sPriorityQueuewithout the object — also a min-heap, but where Java takes aComparator, you negate or use tuples. JavaScript has no built-in heap.
Top-k with a size-k heap
"The 3 most-played" doesn't need every item in order. Keep a min-heap of size k holding the best so far; its root is the weakest of them, and a new item only gets in by beating it:
That's O(n log k) time and O(k) memory. The heap never grows past k, even while scanning a million play counts.
| Operation | Time |
|---|---|
Peek at the minimum, heap[0] |
O(1) |
| Push (sift-up) | O(log n) |
| Pop (sift-down) | O(log n) |
heapify a list |
O(n) |
| Top-k with a size-k heap | O(n log k) |
| Merge k sorted lists, n items in total | O(n log k) |
Idioms & real-world patterns
nlargest, nsmallest and k-way merge
For a one-off top-k, heapq has it built in, and takes a key just like sorted:
The first line gives the tie to whichever title came first. The second uses
(-plays, title) to settle ties alphabetically.
A k-way merge combines k sorted lists. Put each list's first item in a heap, pop the smallest, then push the next item from the list it came from:
The heap never holds more than k entries, so each step is O(log k). The same loop drives job schedulers, event simulations, and Dijkstra's shortest paths in the graphs section.
⚡ Advanced — payloads that can't be compared
When two priorities tie, Python compares the next tuple element, and a dict there
raises TypeError. Put a counter in between so a comparison never reaches the payload:
⚡ Advanced — changing a priority
A heap can't find an item quickly, so you can't edit a play count in place. The standard trick is lazy deletion: push the updated entry, and when a stale one reaches the top, recognise it and throw it away.
🎯 Your turn
Write top_charts(plays, k). plays is the stream of play events, one title per
play. Count them, then use a heap to return the k most-played titles, most plays
first, ties broken alphabetically:
top_charts(["Tides", "Neon", "Tides", "Glass", "Neon", "Tides"], 2)→["Tides", "Neon"]top_charts([], 3)→[]
Hint — count with a dict, heapify a list of (-count, title) pairs, and pop at
most k times.
Then press ▶ Run, tap the Live App try chips to call it with different inputs, and hit ✓ Check. Green = this piece of Tunebox is built. ✅