Videos / DSA

Episode 17 of 22 · DSA, end to end

Priority queues and heaps: the smallest thing, fast

Chapters

1. The desk that never sorts0:00
2. Two obvious answers0:16
3. Sorting over-serves the question0:34
4. Push, top, pop0:51
5. The bar to clear1:06
6. Why not a balanced tree1:25
7. Every stone lighter than the two below1:42
8. Not a search tree1:58
9. The shape rule2:15
10. The tree becomes arithmetic2:31
11. One worked array2:49
12. No pointers, no allocation3:06
13. The bubble that rises3:22
14. Sifting up, traced3:38
15. Popping leaves a hole3:55
16. Sinking, and the smaller child4:11
17. Sinking, traced4:28
18. Why both are log n4:43
19. Bricklayers start at the bottom5:00
20. Floyd's build5:16
21. Height, not depth5:33
22. The series that adds to n5:49
23. Twenty million against one6:07
24. Only if you have it all6:24
25. The sorted tail grows backwards6:40
26. The heapsort loop6:56
27. Why quicksort still wins7:12
28. Ten million, keep ten7:31
29. The inversion that trips people7:48
30. Log k, not log n8:04
31. The flood front8:20
32. Relax, push, ignore the stale8:38
33. Merging k sorted lists8:55
34. The next thing to happen9:13
35. What a heap cannot do9:29
36. The default is a max heap9:47
37. The whole thing10:05

Priority queues and heaps: the smallest thing, fast. A triage desk at a hospital. People arrive in no particular order, and every time a room opens you take the most urgent one waiting. Nobody sorts the whole room. You only ever need

Mark as watchedSaved in this browser only.