Producing a Max Heap
Samuel Marateck (c) 2009
Given the following initial tree, form a heap.
level
z 0
/ \
/ \
x y 1
/ \ / \
a b c d 2
/ \ /\ /
e f g h i 3
Levels 0, 1 and 2 are already in heap form, so no switching is done. Let's
number the nodes.
level
z 1 0
/ \
/ \
x 2 y 3 1
/ \ / \
a 4 b 5 c 6 d 7 2
/ \ /\ /
e f g h i 3
8 9 10
Consider node 8, and call it . Then = /2 or node
4. Since e > a, we switch the letters in nodes 8 and 4 getting:
level
z 1 0
/ \
/ \
x 2 y 3 1
/ \ / \
e 4 b 5 c 6 d 7 2
/ \ /\ /
a f g h i 3
8 9 10
Working our way up this branch, letting = we get =
4. Then = 2. Since e is not greater than x, we set a boolean variable
to true and we stop the switching process that started at node 8. Let's
go to node 9. is now 9, is 9/2 or 4. Since f > e, we switch
the letters in nodes 9 and 4 getting:
level
z 1 0
/ \
/ \
x 2 y 3 1
/ \ / \
f 4 b 5 c 6 d 7 2
/ \ /\ /
a e g h i 3
8 9 10
Let = 4, = 2. Since f is not greater than x, we don't switch
the letters in the nodes and set to true and we stop the switching
process that started at node 9. We continue the process for the higher
numbered nodes, finally getting:
level
z 0
/ \
/ \
x y 1
/ \ / \
f h i d 2
/ \ /\ /
a a b g c 3