Exercise


ABy Admin
May 13'24

Answer

  • 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.

00