7.5 KiB
Построение кучи
В некоторых случаях мы хотим использовать все элементы списка для построения кучи. Этот процесс называется "построением кучи".
Реализация с помощью операции вставки
Сначала создается пустая куча, затем выполняется обход списка, и для каждого элемента выполняется "операция вставки в кучу", т. е. сначала элемент добавляется в основание кучи, а затем для этого элемента выполняется упорядочивание "снизу вверх".
Каждый раз, когда элемент вставляется в кучу, длина кучи увеличивается на единицу. Поскольку узлы добавляются в двоичное дерево последовательно сверху вниз, куча строится "сверху вниз".
Пусть количество элементов равно n, операция вставки каждого элемента занимает O(\log{n}) времени, следовательно, временная сложность этого метода построения кучи составляет O(n \log n).
Реализация через обход с упорядочиванием
На самом деле можно реализовать более эффективный метод построения кучи, который состоит из двух шагов.
- Все элементы списка добавляются в кучу без изменений, при этом свойства кучи еще не выполняются.
- Выполняется обратный обход кучи (обратный порядок обхода по уровням), и для каждого нелистового узла выполняется "упорядочивание сверху вниз".
После упорядочивания каждого узла поддерево с корнем в этом узле становится корректной подкучей. А поскольку используется обратный обход, куча строится "снизу вверх".
Причина выбора обратного обхода заключается в том, что это гарантирует, что поддерево под текущим узлом уже является корректной подкучей, что делает упорядочивание текущего узла эффективным.
Стоит отметить, что поскольку листовые узлы не имеют дочерних узлов, они по своей природе являются корректными подкучами и не требуют упорядочивания. Как показано в следующем коде, последний нелистовой узел является родительским узлом последнего узла, и мы начинаем обратный обход и выполняем упорядочивание с него:
[file]{my_heap}-[class]{max_heap}-[func]{__init__}
Анализ сложности
Далее попытаемся вывести временную сложность второго метода построения кучи.
- Предположим, что количество узлов полного двоичного дерева равно
n, тогда количество листовых узлов составляет(n + 1) / 2, где/-- целочисленное деление вниз. Следовательно, количество узлов, требующих упорядочивания, составляет(n - 1) / 2. - В процессе упорядочивания сверху вниз каждый узел может быть упорядочен максимум до листового узла, поэтому максимальное количество итераций равно высоте двоичного дерева
\log n.
Перемножив эти два значения, получаем временную сложность процесса построения кучи O(n \log n). Но этот расчет неточен, поскольку мы не учли тот факт, что количество узлов на нижних уровнях двоичного дерева намного больше, чем на верхних.
Далее выполним более точный расчет. Чтобы упростить вычисления, предположим, что дано "совершенное двоичное дерево" с количеством узлов n и высотой h. Это предположение не повлияет на правильность результата вычислений.
Как показано на рисунке выше, максимальное количество итераций "упорядочивания узла сверху вниз" равно расстоянию от этого узла до листового узла, а это расстояние и есть "высота узла". Следовательно, можно просуммировать "количество узлов × высота узла" для каждого уровня, получив общее количество итераций упорядочивания для всех узлов.
T(h) = 2^0h + 2^1(h-1) + 2^2(h-2) + \dots + 2^{(h-1)}\times1
Для упрощения этого выражения необходимо использовать знания о числовых последовательностях из средней школы. Сначала умножим T(h) на 2, получим:
\begin{aligned}
T(h) & = 2^0h + 2^1(h-1) + 2^2(h-2) + \dots + 2^{h-1}\times1 \newline
2 T(h) & = 2^1h + 2^2(h-1) + 2^3(h-2) + \dots + 2^{h}\times1 \newline
\end{aligned}
Используя метод разностного вычитания, вычтем верхнее выражение T(h) из нижнего 2 T(h), получим:
2T(h) - T(h) = T(h) = -2^0h + 2^1 + 2^2 + \dots + 2^{h-1} + 2^h
Наблюдая за этим выражением, видим, что T(h) является геометрической прогрессией, можно напрямую использовать формулу суммы, получив временную сложность:
\begin{aligned}
T(h) & = 2 \frac{1 - 2^h}{1 - 2} - h \newline
& = 2^{h+1} - h - 2 \newline
& = O(2^h)
\end{aligned}
Далее, количество узлов совершенного двоичного дерева высотой h равно n = 2^{h+1} - 1, легко получить сложность O(2^h) = O(n). Приведенные выше вычисления показывают, что временная сложность ввода списка и построения кучи составляет O(n), что очень эффективно.