Okay, this is a quick video on building a binary heap, in worst-case linear time, with an elegant proof. Before watching the video, you should understand the introduction to heaps video, where we saw the insertion and heapify methods. Of course, we can build a heap by iterated insertion, that looks great at first, because the heap is small, and insertion is quick. But as the heap gets bigger, elements are inserted deeper down. In the worst case, we insert elements in increasing order, and it will take order n log n time. The last half of the elements inserted are all at about log n depth, and each might need to bubble all the way up to the root. To be fair, iterated insertion gets a bit of a bum rap: for a set of values in random order, most don’t really bubble up too much. Most values end up near the bottom of the tree, and each insertion will, on average, take just a couple of swaps. But, that analysis is definitely not basic. Maybe I will make an advanced video sometime on that. On the other hand, there is a worst-case linear time build-heap operation. It uses that same observation, that most nodes have a small height. It works bottom-up. For our heap definition, we know that every node in a heap will root a valid sub-heap, now no matter what values you give me, any single node with no children looks like a valid heap, taking whatever is given to you, the values that fall into the leaf positions look good on their own. Half of the nodes are leaf nodes, so that ain’t nothin’. Going from the last node, towards the first, we eventually get to a node that is the parent of some other node. This one here in this case. Now considering it as the root of a subheap, it still has the shape of a heap, but its value isn’t bigger than the value in each of its children. It only has one child here. But, that is exactly the place where our max-heapify from the intro video can be used to fix the heap. So use it. For the next n/4 nodes, we will do the same thing, we will use max-heapify to fix all of these small heaps of height 1. Continuing, we fix the n/8 heaps of height 2, the n/16 heaps of height 3, and so on. The one case that was easiest for the iterated insertion, is now the node that looks worst, the root. But for the n/2 nodes that were worst for the iterated insertion, they are now trivial, because they are already heaps to begin with. For our worst-case analysis, we are now dealing with the sum of node heights in the final heap, rather than the sum of node depths, and fewer nodes have a large height. Note, these two methods might not give the same heap, and in fact, given a random starting permutation, they won’t end up even having the same probability distribution over different heaps. Now for the analysis: for each heapify operation, the worst-case runtime is proportional to the starting height of that node. Here, we start off very well, because half of the nodes start at height 0 and can be skipped altogether. A quarter of the nodes move down one level, an eighth move down two levels, and we can generalize the number of nodes at any given height, and sum over all node heights. With a bit of manipulation, this gives us order n worst-case runtime. By magic. Or calculus. Okay, well if want to make this more formal, but also simplify the math, we should first prove something about the structure of the heap. In a heap of n values, there are floor of (n/2^i) nodes of height i or greater. I’m actually going to leave that as an exercise for the viewer. It can be proved with induction. Now, when being heapified, only the values that start at height at least 1 can be moved down even one level. In the worst case, all of those nodes do move down one level. Nodes starting at height 2 [or higher] can each move down a second level. But we have already moved them down one level, so we only have to count one extra to move down that second level. Nodes starting at height 3 [or higher] can move down a third level. This gives us a summation that is easier to bound than the original summation, and a simple proof of the linear runtime for building a heap. Okay, the next standard video to watch is going to be the one on heapsort. At some point, I also expect to get up a few advanced videos, better looking at iterated insertion, as well as a more optimized heapify method. as well as a more optimized heapify method. But for now I’ve got to get my earwax removed. See you next time.