Рубрики

Структуры данных | Куча | Вопрос 8

В минимальной куче с n элементами с наименьшим элементом в корне 7-й наименьший элемент может быть найден во времени
а) (n log n)
б) (П)
с) (журнал N)
г) (1)

Вопрос не был ясен в оригинальном экзамене GATE. Для ясности предположим, что в Min-Heap нет дубликатов, и доступ к элементам кучи ниже root разрешен.
(А)
(Б) б
(С) с
(D) d

Ответ: (Д)
Пояснение: 7-й самый маленький элемент должен быть в первых 7 уровнях. Общее число узлов в любой двоичной куче на первых 7 уровнях составляет не более 1 + 2 + 4 + 8 + 16 + 32 + 64, что является константой. Поэтому мы всегда можем найти 7-й самый маленький элемент в время.

Если Min-Heap разрешено иметь дубликаты, то временная сложность становится равной Log (Log n).

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

Структуры данных | Куча | Вопрос 8

0.00 (0%) 0 votes