Изменения

'''Двоичная куча''' или '''пирамида''' (англ. ''Binary heap'') — такое двоичное [[Дерево, эквивалентные определения|подвешенное дерево]], для которого выполнены следующие три условия:

Удобнее всего двоичную кучу хранить в виде массива <tex>Aa[0..n-1]</tex>, у которого нулевой элемент, <tex>Aa[0]</tex> — элемент в корне, а потомками элемента <tex>Aa[i]</tex> являются <tex>Aa[2i+1]</tex> и <tex>Aa[2i+2]</tex>. Высота кучи определяется как высота двоичного дерева. То есть она равна количеству рёбер в самом длинном простом пути, соединяющем корень кучи с одним из её листьев. Высота кучи есть <tex>O(\log{Nn})</tex>, где <tex>Nn</tex> — количество узлов дерева.

Двоичные кучи используют, например, для того, чтобы извлекать минимум из набора чисел за <tex>O(\log{Nn})</tex>. Они являются частным случаем приоритетных очередей.

Процедура выполняется за время <tex>O(\log{Nn})</tex>.

'''while''' 2 * i + 1 <tex><</tex> Aa.heapSize <font color = "green">// heapSize {{---}} количество элементов в куче</font>

'''if''' right <tex><</tex> Aa.heapSize '''and''' Aa[right] <tex><</tex> A[left]

'''if''' Aa[i] <tex>\leqslant</tex> Aa[j]

swap(Aa[i], Aa[j])

Процедура выполняется за время <tex>O(\log{Nn})</tex>.

'''while''' Aa[i] <tex><</tex> Aa[(i - 1) / 2] <font color = "green">// i <tex>==</tex> 0 {{---}} мы в корне</font> swap(Aa[i], Aa[(i - 1) / 2])

Выполняет извлечение минимального элемента из кучи за время <tex>O(\log{Nn})</tex>.

'''int''' min = Aa[0] Aa[0] = Aa[A.heapSize - 1] Aa.heapSize = Aa.heapSize - 1

Выполняет добавление элемента в кучу за время <tex>O(\log{Nn})</tex>.

Aa.heapSize = Aa.heapSize + 1 Aa[Aa.heapSize - 1] = key siftUp(Aa.heapSize - 1)

==Построение кучи за O(Nn) ==

'''<tex>D</tex>-куча''' {{---}} это куча, в которой у каждого элемента, кроме, возможно, элементов на последнем уровне, ровно <tex>Dd</tex> потомков.

Дан массив <tex>Aa[0.. N n - 1].</tex> Требуется построить <tex>Dd</tex>-кучу с минимумом в корне. Наиболее очевидный способ построить такую кучу из неупорядоченного массива {{---}} сделать нулевой элемент массива корнем, а дальше по очереди добавить все его элементы в конец кучи и запускать от каждого добавленного элемента <math>\mathrm {siftUp}</math>. Временная оценка такого алгоритма <tex> O(Nn\log{Nn})</tex>. Однако можно построить кучу еще быстрее — за <tex> O(Nn) </tex>.

Представим, что в массиве хранится дерево (<tex>Aa[0] - </tex> корень, а потомками элемента <tex>Aa[i]</tex> являются <tex>Aa[2i+1]...Aa[2i+Dd]</tex>). Сделаем <tex> \mathrm {siftDown} </tex> для вершин, имеющих хотя бы одного потомка: от <tex dpi=140>\genfrac {}{}{}{}{Nn}{Dd}</tex> до <tex>0</tex>,{{---}} так как поддеревья, состоящие из одной вершины без потомков, уже упорядочены.

|statement= Время работы этого алгоритма <tex> O(Nn) </tex>.|proof= Число вершин на высоте <tex>h</tex> в куче из <tex>Nn</tex> элементов не превосходит <tex dpi = "160"> \left \lceil \frac{Nn}{Dd^h} \right \rceil </tex>. Высота кучи не превосходит <tex> \log_{Dd}N n </tex>. Обозначим за <tex> H </tex> высоту дерева, тогда время построения не превосходит

<tex dpi = "160"> \sum_{h = 1}^H \limits\frac{Nn}{Dd^h} \cdot D d </tex> <tex dpi = "150"> \cdot h </tex> <tex dpi = "160"> = N n \cdot D d \cdot {\sum_{h = 1}^H \limits}\frac{h}{Dd^h}. </tex>

|statement= <tex dpi = "160"> {\sum_{h = 1}^\infty \limits}\frac{h}{Dd^h} = \frac{Dd}{(D d - 1)^2} . </tex>

Обозначим за <tex>Ss</tex> сумму ряда. Заметим, что<tex dpi = "160"> \frac{n}{Dd^n} = \frac{1}{Dd} \cdot \frac{n - 1}{D d ^{n - 1}} + \frac{1}{Dd^n}. </tex>

\frac{\frac{1}{Dd}}{1 - \frac{1}{Dd}} = \frac{1}{D d - 1}. </tex>

Получаем <tex>Ss</tex> <tex dpi = "160" >=\frac{1}{Dd}</tex> <tex>\cdot S s +</tex> <tex dpi = "160" > \frac{1}{D d - 1}. </tex> Откуда <tex>Ss</tex> <tex dpi = "160"> = \frac{Dd}{(D d - 1)^2}. </tex>

Подставляя в нашу формулу результат леммы, получаем <tex >Nn</tex> <tex dpi = "160">\cdot (\frac {Dd}{D d - 1})^2 </tex> <tex> \leqslant 4 \cdot N n </tex> <tex>=O(Nn).</tex>