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

Question

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

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

Answer 1

Что ж, ваша интуиция была права, что нам нужна дополнительная структура данных для достижения 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).

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

Answer 2

Предполагая, что мы используем 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-й наименьший узел находится в наименьших узлах [k-1].

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