-2
$\begingroup$

I try to insert 4-9-3-7 and 1 (left to right) into a Min-Heap (using array implementation). Then 5 times Remove Smallest Number from this Min-Heap. how many swap between two elements in array occurred?

i try solve this problem as following..

[Add 4: [4

[Add 9: [4, 9

{Add 3: [4, 9, 3] => [3, 9, 4] {one swap of 3 with 4

{Add 7: [3, 9, 4, 7] => [3, 7, 4, 9] {one swap of 7 with 9

{Add 1: [3, 7, 4, 9, 1] => [3, 1, 4, 9, 7] => [1, 3, 4, 9, 7] {two swap of 1 with 7, then with 3

{Remove 1: [1, 3, 4, 9, 7] ~~{one swap}~~> [7, 3, 4, 9] => [3, 7, 4, 9] {one swap of 3 with 7

{Remove 3: [3, 7, 4, 9] ~~{one swap}~~> [9, 7, 4] => [4, 7, 9] {one swap of 4 with 9

{Remove 4: [4, 7, 9] ~~{one swap}~~> [9, 7] => [7, 9] {one swap of 7 with 9

[Remove 7: [7, 9] ~~{one swap}~~> [9

[Remove 9: [9] ~~~~> []

in total i calculate 11 swap. i think my solution is incorrect. any idea? or solution?

$\endgroup$
  • $\begingroup$ Why do you think your solution is incorrect? Why can't you correct it? $\endgroup$ – babou Jun 29 '14 at 11:57
0
$\begingroup$

Yes - 11 swaps. The array state changes will be:

4 9 3       => 3 9 4 
3 9 4 7     => 3 7 4 9 
3 7 4 9 1   => 3 1 4 9 7 
3 1 4 9 7   => 1 3 4 9 7 
1 3 4 9 7   => 7 3 4 9 1 
7 3 4 9     => 3 7 4 9 
3 7 4 9     => 9 7 4 3 
9 7 4       => 4 7 9 
4 7 9       => 9 7 4 
9 7         => 7 9 
7 9         => 9 7 

So, 11 lines = 11 swaps

$\endgroup$
  • $\begingroup$ can you say the swap between two elements in another way? i couldn't understand how you calculate 12? $\endgroup$ – user17973 Jun 6 '14 at 17:30
  • $\begingroup$ I've corrected my answer, and actually the last swap is not needed (when array size = 1) - so it's 11. $\endgroup$ – HEKTO Jun 6 '14 at 17:55
  • $\begingroup$ i really confused. it was a question on entrance exam on 2 days ago. i check more and more... some friends say it's 12. i think it has 11. are you sure? $\endgroup$ – user17973 Jun 6 '14 at 18:02
  • $\begingroup$ You don't actually need to swap first and last element of the array when you extract a minimal element. It's enough to return the first element, then copy the last element into the first position, then cut the last element off and then start the "bubble-down" procedure. This might be a source of differences. $\endgroup$ – HEKTO Jun 6 '14 at 18:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.