O (klogk) для нахождения k-го наименьшего элемента из двоичной кучи

У нас есть двоичная куча n- node, которая содержит n отдельные элементы (самый маленький элемент в корне). При a k<=n найдите алгоритм времени O(klogk), чтобы выбрать kth наименьший элемент из кучи.

O(klogn) очевиден, но не смог определить a O(klogk). Может быть, мы можем использовать вторую кучу, не уверен.

Ответы

Ответ 1

Ну, ваша интуиция была права, что нам нужна дополнительная структура данных для достижения O (klogk), потому что, если мы просто выполняем операции над исходной кучей, термин logn останется в возникающей сложности.

Угадываясь от целевой сложности O (klogk), я чувствую, что создаю и поддерживаю кучу размера k, чтобы помочь мне достичь цели. Как вам известно, создание кучи размера k сверху вниз принимает O (klogk), что действительно напоминает мне о нашей цели.

Ниже приведена моя попытка (не обязательно элегантная или эффективная) в попытке достичь O (klogk):

  • Мы создаем новую мини-кучу, инициализируя ее корень как корень исходной кучи.

  • Мы обновляем новую мини-кучу, удаляя текущий корень и вставляя двух дочерних элементов текущего корня в исходную кучу. Мы повторяем этот процесс k раз.

  • Полученная куча будет состоять из k узлов, корень которых является k-м наименьшим элементом в исходной куче.

Примечания. Узлы в новой куче должны хранить индексы своих соответствующих узлов в исходной куче, а не сами значения node. На каждой итерации шага 2 мы действительно добавляем в новую кучу сеть еще одного node (одна удалена, две вставлены), k итераций которой приведет к нашей новой куче размера k. Во время i-й итерации node, подлежащий удалению, является i-м наименьшим элементом исходной кучи.

Сложность времени: на каждой итерации требуется время O (3 logk) для удаления одного элемента и вставки двух в новую кучу. После k итераций это O (3klog) = O (klogk).

Надеемся, что это решение немного вас вдохновит.

Ответ 2

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

Create a sorted list toVisit, which contains the nodes which we will traverse next. This is initially just the root node.
Create an array smallestNodes. Initially this is empty.
While length of smallestNodes < k:
    Remove the smallest Node from toVisit
    add that node to smallestNodes
    add that node children to toVisit

Когда вы закончите, k-й наименьший node находится в наименьшемNodes [k-1].

В зависимости от реализации toVisit вы можете вставлять в log (k) время и удаление в постоянное время (поскольку вы удаляете только самый верхний node). Это делает O (k * log (k)) total.