# Min-Heap Insertion Problem

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 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?

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

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

• can you say the swap between two elements in another way? i couldn't understand how you calculate 12? – user17973 Jun 6 '14 at 17:30
• I've corrected my answer, and actually the last swap is not needed (when array size = 1) - so it's 11. – HEKTO Jun 6 '14 at 17:55
• 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? – user17973 Jun 6 '14 at 18:02
• 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. – HEKTO Jun 6 '14 at 18:59