A binary max-heap or min-heap, is an ordered structure where some nodes are guaranteed greater than other nodes, e.g. the parent vs two children. A binary heap can be stored in an array , where ,

- given a position i (the parent) , i*2 is the left child, and i*2+1 is the right child.

- ( C arrays begin at position 0, but 0 * 2 = 0, and 0 *2 + 1= 1, which is incorrect , so start the heap at position 1, or add 1 for parent-to-child calculations, and subtract 1 for child-to-parent calculations ).

• try to model this using with a pencil and paper, using 10 random unsorted numbers, and inserting each of them into a "heapsort" array of 10 elements.

• To insert into a heap, end-add and swap-parent if higher, until parent higher.

• To delete the top of a heap, move end-to-top, and defer-higher-child or sift-down , until no child is higher.

• try it on a pen and paper the numbers 10, 4, 6 ,3 ,5 , 11.

• the answer was 11, 5, 10, 3, 4 , 6.

Now try removing each top element of 11, 5, 10, 3, 4, 6 , using end-to-top and sift-down ( or swap-higher-child) to get the numbers in descending order.

• 10, 4, 6, 3, 5, 11 -> 10
• 4, 6,3, 5, 11 -> 10, 4  : 4 is end-added, no swap-parent because 4 < 10.
• 6, 3, 5, 11 -> 10, 4, 6  : 6 is end-added, no swap-parent because 6 < 10.
• 3, 5, 11 -> 10, 4, 6, 3 : 3 is end-added, 3 is position 4 , divide by 2 = 2, 4 at position 2, no swap-parent because 4 > 3.
• 5 , 11 -> 10, 4, 6, 3 , 5 : 5 is end-added , 5 is position 5, divided by 2 = 2, 4 at position 2, swap-parent as 4 < 5; 5 at position 2, no swap-parent because 5 < 10 at position 1.

- 10 , 5, 6, 3, 4

• 11 -> 10, 5, 6, 3, 4, 11 : 11 is end-added, 11 is position 6, divide by 2 = 3, swap 6 with 11, 11 is position 3, swap 11 with 10, stop as no parent.

- 11, 5, 10, 3, 4, 6

- 11 has children 5, 10 ; 5 has children 3 and 4 ; 10 has child 6. Parent always > child.

• 11 leaves * , 5, 10, 3, 4, 6 -> 6 , 5, 10, 3, 4 -> sift-down -> choose greater child 5 (2*n+0) or 10 ( 2*n+1) -> is 6 > 10 ? no -> swap 10 and 6 ->

- 10, 5, *6, 3, 4 -> 4 is greatest child as no +1 child. is 6 > 4 ? yes, stop.

• 10 leaves * , 5 , 6 , 3, 4 -> *4, 5, 6, 3 -> is left(0) or right(+1) child greater -> +1 is greater; is 4 > +1 child ? no , swap

- 6,5, *4, 3 -> *4 has no children so stop.

• 6 leaves *, 5, 4, 3 -> *3, 5, 4 -> +0 child is greater -> is 3 > 5 ? no , so swap -> 5, *3, 4 , *3 has no child so stop.

is

• 5 leaves so 3, 4 -> *4, 3 -> +0 child greatest as no right child -> is 4 > 3 ? no , so exit

• 4 leaves 3 .

• 3 leaves *.

• numbers extracted in descending order 11, 10, 6, 5, 4, 3.

References

Wikibooks contributors. "C Programming/Exercise solutions". Wikibooks. Wikibooks. Retrieved 13 May 2024.