How does heapify work, and how can it build a heap in linear time?
A heap is just a list where every parent is smaller than its children. To turn a list into a heap you take each parent and sift it down until the rule holds again.
def sift_down(data, start, n):
root = start
while True:
child = 2 * root + 1
if child >= n:
break
if child + 1 < n and data[child + 1] < data[child]:
child = child + 1
if data[root] <= data[child]:
break
data[root], data[child] = data[child], data[root]
root = child
So how does it work? A heap is stored as a list, and the tree shape comes from the positions. The children of the item at position p are at position two p plus one and two p plus two. And the parent of the item at position p is at position (p minus one) divided by two, rounded down.
the list 4 8 5 2 1 9
the tree 4
/ \
8 5
/ \ /
2 1 9
And the sift down operation takes one item and moves it down until it is in the right place. You look at its left child, and if the right child is smaller then you take that one instead, because you want the smaller of the two to come up. Then you compare the item with that child and swap them if the child is smaller. And then you carry on with the child as the new parent.
And how can it build a heap in linear time? You start at the last parent and work backwards. The last parent is the item at position (n divided by two) minus one, because the items after that are all leaves. Then you sift down each parent, working from the bottom of the tree up to the root.
And why is it linear and not O of n log n? Because most nodes are near the bottom and they only move a short way. The number of steps is bounded by the sum of the heights of all the nodes, and that sum is O of n. A node at the bottom of the tree moves one step, one above moves two steps, and so on, and there are twice as many of each as you go up.
the level from the bottom the nodes the steps each
------------------------- --------- -------------
the bottom 1 1
one up 2 2
two up 4 3
the total is 1 + 4 + 12 + 24 + ... which is less than 2n
And that is why the library function heapify is O of n while a loop of pushes is O of n log n.
So the rule to remember is this. Work backwards from the last parent, and the total work is linear.
The next two questions in this topic show the sift up and the whole heap.