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

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

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

Источник

2 ответа

Решение

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

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

Следующее - моя попытка (не обязательно элегантная или эффективная) в попытке достичь O(klogk):

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

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

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

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

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

Надеюсь, что это решение вас вдохновляет.

Источник

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

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's children to toVisit

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

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

Источник
Другие вопросы по тегам