Рубрики

ВОРОТА | GATE-CS-2003 | Вопрос 23

GATE

В куче из n элементов с наименьшим элементом в корне, 7-й наименьший элемент может быть найден во времени

(A) Θ (n log n)
(B) Θ (n)
(C) Θ (log n)
(D) Θ (1)

Ответ: (D)
Объяснение:

Чтобы определить k-й наименьший элемент, мы должны сначала извлечь 6 элементов из кучи, а затем корень результирующей кучи будет равен k-й наименьшей. Итоговая сложность времени = 6 операций извлечения-min = 6 * log2n = O (log2n)
Но мы можем найти kth наименьшее из кучи, используя умный подход, извлекая элементы из кучи неразрушающим образом. Мы будем использовать дополнительное пространство для создания новой минимальной кучи, которая будет содержать максимум k элементов в любое время.

Алгоритм:

Инициализируйте корневой элемент new-heap с корнем старой кучи (минимальный элемент)

Для k-1 раза повторите следующее:
Извлеките корень новой минимальной кучи, используя extract-min, и вставьте 2 дочерних элементов извлеченного корня из исходной кучи в новую кучу. Результирующая куча будет содержать k элементов, корень которых будет нашим k-м наименьшим в исходной куче. Это увеличивает новую кучу на единицу при каждом удалении (удаляет один, добавляет два), что означает, что он никогда не будет содержать более K элементов, и поэтому remove-one-add-two будет принимать O (3 * log (K)) , После k итераций это O (3 * k * logk) = O (k * logk).
Чтобы реализовать это, узлы в новой куче должны хранить индексы своих соответствующих узлов в исходной куче, а не сами значения узлов.
Для 7 элементов потребуется 7log7 = O (1), поскольку новая куча создаст только 7 элементов.

Смотрите вопрос 1 из http://espressocode.top/data-structures-and-algorithms-set-9/

Это решение предоставлено Pranjul Ahujka
Тест на этот вопрос

Рекомендуемые посты:

ВОРОТА | GATE-CS-2003 | Вопрос 23

0.00 (0%) 0 votes