Сложность времени для получения минимальных элементов из макс-кучи

Ответ 1

Мой вопрос в том, что если этот ответ правильный.

Нет, это не правильно. Единственная гарантия, которую вы имеете, состоит в том, что каждый node содержит максимальный элемент поддерева ниже. Другими словами, минимальным элементом может быть любой лист в дереве.

Если не правильный ответ?

Правильный ответ - O (n). На каждом шаге вам нужно пройти как левое, так и правое поддерева, чтобы искать минимальный элемент. По сути, это означает, что вам нужно пройти все элементы, чтобы найти минимум.

Ответ 2

Наилучшая сложность O(n). Доказательство эскиза:

• Минимальный элемент может быть абсолютно любым из узлов нижнего уровня (на самом деле он даже не может быть на самом низком уровне, но пусть начнется с них).
• Может быть до n/2 узлов нижнего уровня.
• Все они должны быть проверены, потому что тот, который вы ищете, может оказаться на последнем месте, где вы смотрите. Изучение всех-но-1 из них не говорит вам, является ли последний минимальным или нет.
• Следовательно, требуется Omega(n) экзаменов.

Оценка жесткая, поскольку мы можем сделать это в O(n), игнорируя тот факт, что наш массив оказывается кучей.

Мораль: это, вероятно, называется кучей, потому что (как с кучей одежды на полу вашей спальни) легко попасть наверх и трудно добраться до остальных.

Ответ 3

Минимальный элемент из Max heap:

• поиск на последнем уровне = O (n/2) = O (n)

• заменить искомый элемент на последний элемент и уменьшить размер кучи на 1 = O (1)

• Применить Maxheapify при замене элемента = O (log n)

Общее время = O (n) + O (1) + O (log n) = O (n)

Ответ 4

MINIMUM_ELEMENT → это займет время O (n) в случае Max heap и O (1) в случае Min heap. MAXIMUM_ELEMENT → это займет O (1) раз в случае Max heap и O (n) в случае Min heap.

Ответ 5

Правильный ответ 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) раз

Ответ 6

Наилучшая сложность - O (n).

Вместо того, чтобы не писал здесь много об этом,
Элемент min в MAX-куче и элемент MAX в min-куче
Может быть также на уровне (самый низкий уровень - 1) и не всегда на самом низком уровне.

Объясняю:
поскольку в куче есть опция отсутствия узлов с правой стороны самого нижнего уровня, это может быть не балансирующее (полностью) дерево, из-за чего в нем также есть листья (нижний уровень -1).

что означает, что есть n/2 для проверки. так что в большом члене O он равен O (n).

Примеры для такой ситуации:

• MAX-куча [10,9,1,8,7] (1 - меньшее значение, но не отображается на самом низком уровне)
  
• min-heap [8,10,20,17,15] (20 - максимальное значение, но не отображается на самом низком уровне)