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

В худшем случае k-й наименьший элемент может быть на последнем уровне max-heap. В этом случае время, необходимое для поиска элемента, может уйти в O (n), поскольку в худшем случае может быть n / 2 элементов. на последнем уровне кучи. Или есть ли какой-либо другой алгоритм для поиска k-го наименьшего элемента в куче MAX за время O (logn)?

n = нет. элементов в куче


algorithm heap heapsort
person Olivia Pearls    schedule 02.02.2020    source источник
comment
Я думаю, это зависит от представления дерева. Если каждый узел хранит количество листьев под ним, вы можете использовать двоичный поиск, чтобы получить O (log n). Также см. здесь, чтобы узнать о связанных обсуждение.   -  person hilberts_drinking_problem    schedule 02.02.2020

Ответы (1)


arrow_upward
0
arrow_downward

да. Вы можете сделать это за O (k log n). Чтобы объяснить процедуру, рассмотрим пример массива [30,20,10,9,7,5].

Структура кучи для этого определяется следующим образом:

Макс. Куча

Теперь у нас есть следующий шаблон.

  • 1-й минимальный элемент -> 6-й максимальный элемент
  • 2-й минимальный элемент -> 5-й максимальный элемент
  • 3-й минимальный элемент -> 4-й максимальный элемент
  • ..
  • ..
  • ..
  • k-й минимальный элемент -> (n-k + 1) -й максимальный элемент

Например, в нашем примере 5-й минимальный элемент -> 2-й максимальный элемент -> 20

person Maruthi Adithya    schedule 02.02.2020
comment
Я думаю, что O (klogn) определенно отличается от O (log n) - person Boris Strandjev; 02.02.2020
comment
@BorisStrandjev Да. Даже чтобы найти k-й max элемент в max-куче, требуется O (k log n). Кроме того, когда k равно O (1), это ~ O (log n), что намного лучше, чем O (n) - person Maruthi Adithya; 02.02.2020
comment
Это только O (log n), когда k равно O (1). k ‹< n ​​недостаточно. Но когда k равно O (1), поиск k-го наименьшего элемента составляет O (1), потому что в дереве есть только O (2 ^ k) мест, где он может быть. - person kaya3; 02.02.2020
comment
Существуют решения найти k-й элемент O (log n) независимо от k в [0 .. n]. Это то, что такое O (log n) и что спрашивает OP - person Boris Strandjev; 02.02.2020
comment
@SohamChatterjee Не могли бы вы прояснить это значение k? - person Maruthi Adithya; 02.02.2020
comment
У нас есть стандартные алгоритмы для извлечения k-го по величине элемента за время O (klog n). k-й наименьший элемент - это (n-k + 1) -й наибольший элемент. Итак, мы можем извлечь n-k + 1 элементов из max-heap; что дало бы временную сложность O ((n-k) logn). Я хочу, чтобы наименьший элемент находился за время O (logn) из максимальной кучи. - person Olivia Pearls; 02.02.2020
comment
@SohamChatterjee Я не думаю, что вы можете сделать лучше, чем это. Во всяком случае, не уверен. Но это лучше, чем O (n) - person Maruthi Adithya; 02.02.2020