Complete Binary Max Heap??

Question

http://en.wikipedia.org/wiki/Image:Max-heap.png

That tree has 4 level, and it has 9 items. I know 9 items, but how do I turn it into 4 levels using an equation?

Answer 1

max n = 2^L - 1
levels = int(log2(n + 1)) + 1

Assume a randiom distribution of values. At each level, you have a parent, P, a larger child, LC and a smaller child, SC
Starting at the owest level,
If P < LC, swap P and LC

Using the sample distribution,
. . . . . 45
. . .60 . . 36
. 90 44 80 70
73 17
90 > 73, so all is well
going up 1 level,
60 < 90 and 36 < 80, so swap these pairs:
. . . . . 45
. . . 90 . . . 80
. 60 44 36 70
73 17
45 < 90 so swap
. . . . . 90
. . . 45 . . . 80
. 60 44 36 70
73 17
45 <60 so swap:
. . . . . 90
. . . 60 . . . 80
. 45 44 36 70
73 17
45 < 73 so swap:
. . . . . . 90
. . . 60 . . . . 80
. 73 44 . 36 70
45 17
60 < 73 so swap:
. . . . . . 90
. . . 73 . . . . 80
. 60 44 . 36 70
45 17