Interview Cake In the simpler analysis, we said that each of the n elements in the tree might have to move down times, since the tree had height .
That's true, but it's a bit of an overestimate. For instance, all of the leaf nodes at the bottom of the tree won't have to move down at all. And the parents of those nodes will only move down once. In fact, there's only one node that might move down times: the root node.
Since binary heaps are based on complete binary trees, there will be n/2 nodes in the bottom level, n/4 nodes in the second-to-last level, etc. Each time we go up a level we cut the number of nodes in half.
With that in mind, let's look at how many downward moves it'll take to transform the tree into a heap. We'll say the tree height is h and level 1 is the root.
| Level | Nodes | Moves | Work |
|---|---|---|---|
| h | \frac{n}{2} | 0 | 0 |
| h - 1 | \frac{n}{4} | 1 | \frac{n}{4} |
| h - 2 | \frac{n}{8} | 2 | 2 * \frac{n}{8} |
| h - 3 | \frac{n}{16} | 3 | 3 * \frac{n}{16} |
| \vdots | \vdots | \vdots | \vdots |
| 1 | 1 | h | h |
Adding this all up, we've got:
Alternatively, this can be expressed as a summation:
It turns out that this sequence converges to n/2. That's .
Our heapify algorithm works from the bottom of the tree upwards. What if we worked from the top of the tree downwards—having each child "bubble up" to replace its parent?
It turns out to be more expensive—. Can you figure out why? (Hint: how many leaf nodes do we have, and how many times might each one move?)
See also:
Interview coming up?
Get the free 7-day email crash course. You'll learn how to think algorithmically, so you can break down tricky coding interview questions.
No prior computer science training necessary—we'll get you up to speed quickly, skipping all the overly academic stuff.
No spam. One-click unsubscribe whenever.
You're in! Head over to your email inbox right now to read day one!
