Алгоритм сортировки кучи

Question

У меня есть куча из двоичного дерева. Это не массив. Мне было интересно, как бы я пошел сортировать это. Я знаю, что мне нужно взять последний узел, поместить его в корень и создать пузырек кучи. Эта часть у меня есть. У меня проблема в том, чтобы узнать, как получить новый последний узел. Есть ли алгоритм, чтобы найти последний узел? Нужно ли отслеживать каждый из родительских узлов на каждом узле?

Спасибо.

Answer 1

Предполагая, что дерево, с которого вы начинаете, является полным деревом, я бы посмотрел, можете ли вы отслеживать высоту каждого узла.

Затем, когда вы выполняете итерацию по дереву в поисках следующего дочернего элемента для удалениявы делаете проверку на каждом узле.Если Lh> Rh, идите налево, иначе - направо.Единственное предостережение, которое я имею в связи с этой идеей, заключается в том, что когда вы берете этот узел, вам необходимо обновить все высоты.Которые добавляют стоимость O (log n).Но так как вы пересекаете дерево, которое является тэтой (log n), это не слишком большая асимптотическая сделка.