Рубрики

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

В двоичной максимальной куче, содержащей n чисел, самый маленький элемент может быть найден во времени (GATE CS 2006)
(A) 0 (n)
(B) O (logn)
(С) 0 (логлогия)
(D) 0 (1)

Ответ: (А)
Объяснение: В максимальной куче самый маленький элемент всегда присутствует в листовом узле. Поэтому нам нужно проверить все листовые узлы на минимальное значение. В худшем случае сложность будет O (n)

         12
        /  \
      /      \
    8         7
   / \        / \
 /     \    /     \
2      3   4       5

Тест на этот вопрос

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

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

0.00 (0%) 0 votes