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