Revision as of 21:49, 13 May 2024 by Admin
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.