Обмен Heapsort с помощью Insertion Sort?

Question

Можно ли использовать сортировку вставки в heapsort для замены метода подкачки или обмена?

Обычно подкачка требует минимум 3 шага:

temp = a
a = b
b = temp

Мой друг сказал, чтоможно использовать сортировку вставки, чтобы уменьшить своп до одной операции вместо трех.Это так?

Answer 1

Я думаю, что он имеет в виду, что когда вы просеиваете (или поднимаете) элемент в куче, вы не сохраняете этот элемент, пока не найдете, куда он должен идти.Таким образом, существует только одна операция для свопинга: сохранение меньшего элемента в его новой позиции в куче.Процесс сродни процессу вставки, когда вы перемещаете элемент в его отсортированное место в начале массива.