Heap sort using only insert and remove?

Question

I am doing an review on my Algorithm exam, and here's a problem I found in old exam without sample solution. I am not sure what would be a reasonable answer to this question:

Using a heap and its two operations Remove and Insert,  design an algorithm which sorts an array of size n in O(nlogn) time.

To me, this problem looks like a simple heap-sorting problem, and I think my answer is just:
- 1) Insert every element in to a min heap
- 2) remove everything in the heap from the top and put them in a array in order...

Not sure this is what they want, anyone has any idea please share.

Answer 1

I think that you are on right track. See here, slide 39.