18
правок
Изменения
→decreaseKey: опечатка
{{Определение
|definition='''Условие левосторонней кучи'''. Пусть <tex>dist(u)</tex> {{---}} расстояние от вершины <tex>u</tex> до ближайшей свободной позиции в ее поддереве. У пустых позиций <tex>dist = 0</tex>. Тогда потребуем для любой вершины <tex>u : dist(u.left)\geqslant dictdist(u.right)</tex>.}}
Если для какой- то вершины это свойство не выполняется, то это легко устраняется: можно за <tex>O(1)</tex> поменять местами левого и правого ребенка, что не повлияет на порядок кучи.
|id=lemma2
|about=2
|statement=У левостороннего дерева с правой ветвью длинны длины <tex>h</tex> количество узлов <tex>n \geqslant 2^{h} - 1</tex>.
|proof=Индукция по h.
Пусть на <tex> i </tex>-ом шаге алгоритма в нашем списке остались только кучи размера <tex> 2^i </tex>. На нулевом шаге у нас <tex> n </tex> куч из одного элемента, и на каждом следующем количество куч будет уменьшаться вдвое, а число вершин в куче будет увеличиваться вдвое. Слияние двух куч из <tex> n_i </tex> элементов выполняется за <tex> O(\log{n_i}) </tex>. Поэтому построение будет выполняться за
<tex dpi = 130> \sum\limits_{i = 1}^{\left\lceil \log{n} \right\rceil} \genfrac{}{}{}{0}dfrac{n \cdot \log{n_i}}{2^i} = n \cdot \sum\limits_{i = 1}^{\left\lceil \log{n} \right\rceil} \genfrac{}{}{}{0}dfrac{\log{2^i}}{2^i} = n \cdot \sum\limits_{i = 1}^{\left\lceil \log{n} \right\rceil} \genfrac{}{}{}{0}dfrac{i}{2^i}
</tex>
Покажем, что сумма {{---}} <tex> O(1) </tex>, тогда и алгоритм будет выполняться за <tex> O(n) </tex>. Найдём сумму [[Определение суммы числового ряда|ряда]], заменив его на эквивалентный [[Определение функционального ряда|функциональный]]:
<tex dpi = 130> \sum\limits_{i = 1}^{\left\lceil \log{n} \right\rceil} \genfrac{}{}{}{0}dfrac{i}{2^i} < \sum\limits_{i = 1}^{\infty } \genfrac{}{}{}{0}dfrac{i}{2^i} \\
f(x) = \sum\limits_{i = 1}^{\infty } \Bigl. i \cdot x^i \Bigr|_{x = \frac{1}{2}} \\
~\genfrac{}{}{}{0}dfrac{f(x)}{x} = \sum\limits_{i = 1}^{\infty } i \cdot x^{i - 1} = \sum\limits_{i = 1}^{\infty } (x^i)' = \left(\sum\limits_{i = 1}^{\infty } x^i\right)' \\~\int\genfrac{}{}{}{0}dfrac{f(x)}{x} = \sum\limits_{i = 1}^{\infty } x^i =~\genfrac{}{}{}{0}dfrac{1}{1 - x} - 1 \\~\genfrac{}{}{}{0}dfrac{f(x)}{x} = \left(\genfrac{}{}{}{0}dfrac{1}{1 - x} - 1\right)' = \genfrac{}{}{}{0}dfrac{1}{(1 - x)^2} \\~f(x) = \genfrac{}{}{}{0}dfrac{x}{(1 - x)^2}
</tex>
После подстановки <tex> x = \genfrac{}{}{}{0}dfrac{1}{2} </tex> получаем, что сумма равна <tex> 2 </tex>. Следовательно, построение кучи таким образом произойдёт за <tex> O(n) </tex>.
==Преимущества левосторонней кучи==
Нигде не делается уничтожающих присваиваний. Не создается новых узлов в <tex>\mathrm{merge}</tex>. Эта реализация слияния является функциональной — ее легко реализовать на функциональном языке программирования. Также данная реализация <tex>\mathrm{merge}</tex> является персистентной.
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Приоритетные очереди]]
[[Категория: Структуры данных]]
