I'm studying heap sort and was presented with the following question.

What is the minimum number of items that must be exchanged during a remove the maximum operation in a heap of size N? Give a heap of size 15 for which the minimum is achieved.

There should be at minimum two sorts for this problem which I understand. However, I have trouble figuring out the answer for the second part of the problem,

Answer the same questions for two and three successive remove the maximum operations.

Would the answer also be 2 because the same process is taking place in which we find the child with the bigger key and see if the child needs to be promoted?

  • $\begingroup$ What are your thoughts? Have you tried proving your answer correct? We don't want to just do your exercise for you, or just check your answer/tell you whether your guess is correct -- but if the exercise helped you realize there is some conceptual issue you're not sure about, then asking about that conceptual question could be a good question. As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$ – D.W. Oct 19 '15 at 20:26

Your Answer

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

Browse other questions tagged or ask your own question.