ВОРОТА | ВОРОТА КС 2021 | Набор 2 | Вопрос 12

Пусть H — бинарная мини-куча, состоящая из n элементов, реализованная в виде массива. Какова временная сложность оптимального алгоритма поиска максимального элемента в H в наихудшем случае?
(А) Θ(1)
(В) Θ(logn)
(С) Θ(n)
(D) Θ(nlogn)

Ответ: (С)
Объяснение: в случае минимальной кучи, если нам нужно узнать максимальный элемент, чем он должен присутствовать в конечных узлах, поэтому в худшем случае нам нужно искать до конечных узлов, мы не можем выполнять здесь двоичный поиск, потому что это не BST и кучи не нужны быть в отсортированном порядке, поэтому в худшем случае это будет (n/2)+1. При нормализации это будет O (n), что является вариантом 3.

Refer — Максимальный элемент в минимальной куче

Викторина этого вопроса