Сортировка кучи с использованием только вставки и удаления?

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. 

Для меня эта проблема выглядит как простой кучи сортировки проблемы, и я думаю, что мой ответ просто:
- 1) Вставьте каждый элемент в минусовой куче
- 2) удалите все в куче сверху и поместите их в массив по порядку ...

Не уверен, что это то, что они хотят, любой может подумать, пожалуйста, поделиться им.

Answer 1

Я думаю, что вы на правильном пути. См. here, слайд 39.