Какова сложность удаления в двоичных кучах в худшем случае?

63
8
1
Лучший ответ
63

Предполагая, что вы удаляете минимальное значение из минимальной кучи или максимальное значение из максимальной кучи, оно будет прямо пропорционально количеству уровней в дереве.

С точки зрения двоичной кучи, сколько существует уровней? Бинарная куча по определению является полным двоичным деревом. То есть все уровни, кроме последнего (самого глубокого), должны быть заполнены.

При условии, что емкость каждого i-го уровня удваивается, количество уровней в дереве будет примерно равно количеству раз, которое вы можете разделить N пополам, или, другими словами, логарифмическая основа 2 из N, где N - это число элементы в дереве.

Выше дерева куча может содержать 15 узлов. Таким образом, уровни могут быть выражены как:

L ≈ l o g 2 (N) = l o g 2 (15) ≈ 4 L ≈ l o g 2 (N) = l o g 2 (15) ≈ 4 л \ приблизительно log_2 (N) = log_2 (15) \ приблизительно 4

Конечно, мы должны округлить, потому что не может быть 3,9 уровней.

Чтобы удалить узел, мы извлекаем значение сверху, меняем последнее значение в его старое положение, затем продолжаем менять местами, чтобы опуститься.

Таким образом, при свопинге с вершины в худшем случае нам потребуется пройти весь путь назад вниз по дереву - которое мы уже определили, чтобы иметь максимальную глубину O (log 2 (N)) O (log 2 (N)) O (log_2 (N)). Таким образом, удаление в худшем случае является логарифмическим.

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

ответил(а) 2020-06-08T15:10:56+03:00 11 месяцев, 1 неделя назад
Ваш ответ
Введите минимум 50 символов
Чтобы , пожалуйста,
Выберите тему жалобы:

Другая проблема