Удаление 2-го наименьшего элемента из двоичной Max-Heap

Question

Этот вопрос похож на этот. Разница в том, что у меня есть бинарная Max-Heap вместо Min-Heap. Что делает вопрос совершенно другим.

Мои мысли:

1) Я прохожу все узлы, чтобы найти второй наименьший элемент, это займет O (n)

2) Когда я нахожу 2-й наименьший элемент, я поднимаю этот элемент вверх, меняя его родительский элемент до тех пор, пока он не достигнет корня, это займет O (logn)

3) Я удаляю элемент из корня и беру крайний правый элемент и сохраняю его в корневом расположении (обычная операция удаления кучи), это займет O (logn)

Всего будет O (n) + O (logn) + O (logn), что составляет O(n).

Отредактировано: добавлено двоичное

Есть ли лучшее решение, чем это?

Answer 1

Почему бы вам не сохранить небольшой массив с двумя элементами, чтобы сохранить копию двух самых маленьких элементов?

Затем все операции изменяются только с O(1) шагами, и вы можете предоставить ответ в постоянное время.

Answer 2

Второй наименьший элемент является либо листом, либо родителем листа, и лист является единственным его потомком.

Как удалить второй самый маленький элемент:

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

Таким образом, O(n)+O(log(n)) - это все еще O (n), но с меньшим количеством сравнений.

Answer 3

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

Однако вы можете уменьшить количество максимальных узлов, к которым нужно перейти 1/2 * nи, по сути, удвоить скорость алгоритма. [еще O(n) домен], так как 2-й наименьший элемент в максимальной куче имеет не более одного сына, так что вы можете пройти только по листьям (n/2 из них), и не более одного элемента, который имеет только одного сына. (помните, что двоичная куча - это массив, представляющий полное дерево, поэтому не более одного элемента имеет ровно одного сына).

Можно также немного улучшить шаг удаления, но я сомневаюсь, что это окажет какое-либо существенное влияние), так что я бы не стал прикладывать усилия к этому.