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

Question

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

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

Answer 1

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

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

Сейчас , у нас есть следующий шаблон:

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

Например, в нашем примере элемент 5th min -> элемент 2nd max -> 20