Unit 12 · Module 3 · Complexity and data structures
Trees and heaps — balancing, and the priority queue
A binary search tree that grows the wrong way is just a slow list. A heap gives up full order to make "give me the smallest" almost free.
Unit 12 of the free 49-unit computer-science course, in complexity and data structures. 1 topic to watch or read and a short self-check.
Watch or read
One topic makes up this unit. Take each one whichever way suits you, then answer the questions below.
Heaps and priority queues
A binary heap drains 100,000 background jobs in 54.8 ms where a plain list with min() takes 72 seconds — a 1,300x gap from one rule: every parent is smaller than its children. Here is how the tree is never actually built, why sift up and sift down are the only two moves, why building bottom-up is O(n) and not O(n log n), and the four things a heap will not do for you.
Self-check — 6 questions
Answer alone, at 2am, with no interviewer in the room.