Двоичная куча из n элементов может быть создана за O (n) время с использованием умного алгоритма и умного анализа.В дальнейшем я просто расскажу о том, как это работает, при условии, что у вас есть явные узлы и явные левый и правый дочерние указатели, но этот анализ по-прежнему совершенно верен, когда вы сжимаете его в массив.
Алгоритм работает следующим образом.Начнем с того, что берем около половины узлов и рассматриваем их как синглтон-максимальные кучи - поскольку существует только один элемент, дерево, содержащее только этот элемент, должно автоматически быть максимальной-кучей.Теперь возьмите эти деревья и соедините их друг с другом.Для каждой пары деревьев возьмите одно из значений, которые вы еще не использовали, и выполните следующий алгоритм:
Сделайте новый узел корнем кучи, оставив его слева иправые дочерние указатели ссылаются на две максимальные кучи.
Хотя у этого узла есть дочерний элемент, который больше его, поменяйте местами дочерний элемент с его более крупным дочерним элементом.
Я утверждаю, что в результате этой процедуры создается новая максимальная куча, содержащая элементы двух входных максимальных куч, и это происходит за время O (h), где h - высота двух куч.Доказательством является индукция высоты кучи.В качестве базового случая, если подголовки имеют нулевой размер, то алгоритм немедленно завершается с помощью одиночной максимальной кучи, и это происходит за время O (1).Для индуктивного шага предположим, что для некоторого h эта процедура работает с любыми подпучками размера h и рассмотрим, что происходит, когда вы выполняете его для двух куч размера h + 1. Когда мы добавляем новый корень, чтобы объединить два поддерева размераh + 1, есть три возможности:
Новый корень больше, чем корни обоих поддеревьев.Тогда в этом случае мы имеем новую максимальную кучу, так как корень больше, чем любой из узлов в любом поддереве (транзитивностью)
Новый корень больше, чем один дочерний элемент именьше, чем другие.Затем мы меняем корень с большим дочерним элементом и рекурсивно выполняем эту процедуру снова, используя старый корень и два дочерних дерева, каждое из которых имеет высоту h.По индуктивной гипотезе это означает, что поддерево, в которое мы обменивались, теперь является максимальной кучей.Таким образом, общая куча - это максимальная куча, поскольку новый корень больше, чем все в поддереве, с которым мы обменивались (так как он больше, чем добавленный нами узел, и уже был больше, чем все в этом поддереве), и он также больше, чем всев другом поддереве (так как он больше, чем корень, а корень был больше, чем все в другом поддереве).
Новый корень меньше, чем оба его потомка.Затем, используя слегка измененную версию приведенного выше анализа, мы можем показать, что результирующее дерево действительно является кучей.
Более того, поскольку на каждом шаге высота дочерних куч уменьшается на единицуобщее время выполнения для этого алгоритма должно быть O (h).
На данный момент, у нас есть простой алгоритм для создания кучи:
- Взять около половиныузлы и создавать одиночные кучи.(Вы можете явно вычислить, сколько узлов здесь потребуется, но это примерно половина).
- Соедините эти кучи, затем объедините их вместе, используя один из неиспользуемых узлов и описанную выше процедуру.
- Повторяйте шаг 2 до тех пор, пока не останется одна куча.
Поскольку на каждом шаге мы знаем, что кучи, которые у нас есть, являются действительными максимальными кучами, в конечном итоге это приводит к действительной общей максимальной куче.Если мы разберемся с тем, как мы выбираем, сколько синглтон-куч нужно создать, это также приведет к созданию полного двоичного дерева.
Однако, похоже, что это должно выполняться за O (n lg n) времени, поскольку мы выполняем O (n) слияний, каждое из которых выполняется за O (h), и в худшем случае высота деревьев, которые мы объединяем, равна O (lg n).Но эта граница не является жесткой, и мы можем добиться большего, если будем более точными в анализе.
В частности, давайте подумаем о том, насколько глубоки все деревья, которые мы объединяем.Около половины кучи имеют нулевую глубину, затем половина того, что осталось, имеет глубину один, затем половина того, что осталось, имеет глубину два, и т. Д. Если мы суммируем это, мы получим сумму
0 * n/ 2 + 1 * n / 4 + 2 * n / 8 + ... + nk / (2 k ) = Σ k = 0 ⌈log n⌉ (nk / 2 k ) = n Σ k = 0 ⌈log n⌉ (k / 2 k + 1 )
Это верхний предел количества сделанных свопов.Каждый своп требует не более двух сравнений.Поэтому, если мы умножим вышеупомянутую сумму на два, мы получим следующее суммирование, которое ограничивает число сделанных перестановок:
n Σ k = 0 ∞ (k / 2 k )
Суммирование здесь представляет собой суммирование 0/2 0 + 1/2 1 + 2/2 2 + 3/2 3 + ....Это известное суммирование, которое можно оценить несколькими различными способами.Один из способов оценить это - на этих слайдах лекций, слайды 45-47 .В итоге получается ровно 2n, что означает, что число сравнений, которые в итоге будут сделаны, определенно ограничено сверху 3n.
Надеюсь, это поможет!