Меня спросили в интервью:
Какова наилучшая временная сложность в получении минимального элемента (ов) из max-heap?
Я ответил как O (1), предполагая, что размер кучи известен, а куча реализована как двоичная куча с использованием массива. Таким образом, согласно моему предположению, минимальное значение равно heap_array[heap_size].
Мой вопрос в том, что если этот ответ правильный. Если нет, то какой правильный ответ?
Мой вопрос в том, что если этот ответ правильный.
Нет, это не правильно. Единственная гарантия, которую вы имеете, состоит в том, что каждый node содержит максимальный элемент поддерева ниже. Другими словами, минимальным элементом может быть любой лист в дереве.
Если не правильный ответ?
Правильный ответ - O (n). На каждом шаге вам нужно пройти как левое, так и правое поддерева, чтобы искать минимальный элемент. По сути, это означает, что вам нужно пройти все элементы, чтобы найти минимум.
Наилучшая сложность O(n). Доказательство эскиза:
n/2 узлов нижнего уровня.Omega(n) экзаменов.Оценка жесткая, поскольку мы можем сделать это в O(n), игнорируя тот факт, что наш массив оказывается кучей.
Мораль: это, вероятно, называется кучей, потому что (как с кучей одежды на полу вашей спальни) легко попасть наверх и трудно добраться до остальных.
Минимальный элемент из Max heap:
поиск на последнем уровне = O (n/2) = O (n)
заменить искомый элемент на последний элемент и уменьшить размер кучи на 1 = O (1)
Применить Maxheapify при замене элемента = O (log n)
Общее время = O (n) + O (1) + O (log n) = O (n)
MINIMUM_ELEMENT → это займет время O (n) в случае Max heap и O (1) в случае Min heap. MAXIMUM_ELEMENT → это займет O (1) раз в случае Max heap и O (n) в случае Min heap.
Правильный ответ O (n) 1), чтобы найти минимальный элемент из максимальной кучи. Найти nth max (который является ничем иным, как минимальным элементом), который сначала возьмет n (n-1)/2 сравнений == O (n ^ 2) 2) вообще это массив. Чтобы найти минимальный элемент, примените выбор сортировки 1-го прохода, который займет O (n) времени. 3) удалить один за другим (до) n элементов в максимальной куче (это только поиск), что займет время O (nlogn). Среди 3 способов лучшим является O (n). Таким образом, правильный ответ будет O (N) раз
Наилучшая сложность - O (n).
Вместо того, чтобы не писал здесь много об этом,
Элемент min в MAX-куче и элемент MAX в min-куче
Может быть также на уровне (самый низкий уровень - 1) и не всегда на самом низком уровне.
Объясняю:
поскольку в куче есть опция отсутствия узлов с правой стороны самого нижнего уровня, это может быть не балансирующее (полностью) дерево, из-за чего в нем также есть листья (нижний уровень -1).
что означает, что есть n/2 для проверки. так что в большом члене O он равен O (n).
Примеры для такой ситуации: