Изменения
символ сравнения не отображался
==Определение==
{{Определение
|definition=
'''Двоичная куча''' или '''пирамида''' (англ. ''Binary heap'') — такое двоичное [[Дерево, эквивалентные определения|подвешенное дерево]], для которого выполнены следующие три условия:
* Значение в любой вершине не меньше, (если куча для максимума), чем значения её потомков.
* На <tex>i</tex>-ом слое <tex>2^i</tex> вершин, кроме последнего. Слои нумеруются с нуля.
* Последний слой заполнен слева направо (как показано на рисунке)
}}
[[Файл:HeapMin_heap.pngpng|thumb|325px|Пример кучи для максимумаминимума]][[Файл:Min_heap_array.png|thumb|325px|Хранение кучи в массиве, красная стрелка {{---}} левый сын, зеленая {{---}} правый]]Удобнее всего двоичную кучу хранить в виде массива <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> \mathrm {siftDown} </tex>.
Работа процедуры: если <tex>i</tex>-й элемент меньше, чем его сыновья, всё поддерево уже является кучей, и делать ничего не надо. В противном случае меняем местами <tex>i</tex>-й элемент с наименьшим из его сыновей, после чего выполняем <tex> \mathrm {siftDown} </tex> для этого сына.
Процедура выполняется за время <tex>O(\log{Nn})</tex>.
====siftDown====
<codestyle="display:inline-block">
'''function''' siftDown(i : '''int'''):
'''while''' 2 * i + 1 < Aa.heapSize <font color = "green">// <tex>heapSize</tex> {{---}} количество элементов в куче</font> left = A[2 * i + 1] <font color = "green">// left {{---}} левый сын</font> '''if''' 2 * i + 2 < A.heapSize '''and''' A[right = 2 * i + 2] <= left <font color = "green">// A[2 * i + 2] right {{---}} правый сын</font> swap(A j = left '''if''' right < a.heapSize '''and''' a[2 * i + 2right], A< a[ileft]) i j = 2 * i + 2right '''else if''' Aa[2 * i + 1] < A= a[ij] '''break''' swap(Aa[2 * i + 1], Aa[ij]) i = 2 * i + 1 '''else''' breakj
</code>
====siftUp====
Если значение измененного элемента уменьшается, то свойства кучи восстанавливаются функцией <tex> \mathrm {siftUp} </tex>.
Работа процедуры: если элемент больше своего отца, условие 1 соблюдено для всего дерева, и больше ничего делать не нужно. Иначе, мы меняем местами его с отцом. После чего выполняем <tex> \mathrm {siftUp} </tex>
для этого отца. Иными словами, слишком большой маленький элемент всплывает наверх.Процедура выполняется за время <tex>O(\log{Nn})</tex>. <codestyle="display:inline-block">
'''function''' siftUp(i : '''int'''):
'''while''' Aa[i] < Atex><</tex> a[(i - 1) / 2] <font color = "green">// i <tex>== </tex> 0 {{---}} мы в корне</font> swap(Aa[i], Aa[(i - 1) / 2])
i = (i - 1) / 2
</code>
===Извлечение минимального элемента===
Выполняет извлечение минимального элемента из кучи за время <tex>O(\log{Nn})</tex>.
Извлечение выполняется в четыре этапа:
# Значение корневого элемента (он и является минимальным) сохраняется для последующего возврата.
# Сохранённый элемент возвращается.
<codestyle="display:inline-block">
'''int''' extractMin():
</code>
===Добавление нового элемента===
Выполняет добавление элемента в кучу за время <tex>O(\log{Nn})</tex>.
Добавление произвольного элемента в конец кучи, и восстановление свойства упорядоченности с помощью процедуры <math> \mathrm {siftUp} </math>.
<codestyle="display:inline-block">
'''function''' insert(key : '''int'''):
</code>
===Построение кучи за O(Nn) ===
{{Определение | definition =
'''<tex>D</tex>-куча''' {{---}} это куча, в которой у каждого элемента, кроме, возможно, элементов на последнем уровне, ровно <tex>Dd</tex> потомков.
}}
Дан массив <tex>Aa[0.. N n - 1].</tex> Требуется построить <tex>Dd</tex>-кучу с минимумом в корне. Наиболее очевидный способ построить такую кучу из неупорядоченного массива {{---}} сделать нулевой элемент массива корнем, а дальше по очереди добавить все его элементы (сделать в конец кучи и запускать от каждого добавленного элемента <texmath> \mathrm {siftDownsiftUp} </texmath> для каждого). Временная оценка такого алгоритма <tex> O(Nn\log{Nn})</tex>. Однако можно построить кучу еще быстрее — за <tex> O(Nn) </tex>. Представим, что в массиве хранится дерево (<tex>Aa[0] - </tex> корень, а потомками элемента <tex>Aa[i]</tex> являются <tex>Aa[2idi+1]...Aa[2idi+Dd]</tex>). Сделаем <tex> \mathrm {siftDown} </tex> для вершин, имеющих хотя бы одного потомка, начиная с конца (: от <texdpi=140> \dfrac{n - 1}{d}</tex> до <tex>0</tex>) (,{{---}} так как поддеревья, состоящие из одной вершины без потомков, уже упорядочены).
{{Лемма
|statement= На выходе получим искомую кучу.
}}
{{Лемма
|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>
|proof=
Обозначим за <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>
<tex dpi = "160">{\sum_{n = 1}^\infty \limits}\frac{1}{d^n}</tex> {{---}} это сумма бесконечной убывающей геометрической прогрессии, и она равна <tex dpi = "160">
\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>
}}
Псевдокод алгоритма:
<code style="display:inline-block">
'''function''' heapify():
'''for''' i = a.heapSize / 2 '''downto''' 0
siftDown(i)
</code>
===Слияние двух куч===
Даны две кучи <tex>a</tex> и <tex>b</tex>, размерами <tex>n</tex> и <tex>m</tex>, требуется объединить эти две кучи.
====Наивная реализация====
Поочередно добавим все элементы из <tex>b</tex> в <tex>a</tex>. Время работы {{---}} <tex>O(m \log(n+m))</tex>.
<code style="display:inline-block">
'''function''' merge(a, b : '''Heap'''):
'''while''' b.heapSize <tex>\neq</tex> 0
a.insert(b.extractMin())
</code>
====Реализация с помощью построения кучи====
Добавим все элементы кучи <tex>b</tex> в конец массива <tex>a</tex>, после чего вызовем функцию построения кучи. Процедура выполняется за время <tex>O(n + m)</tex>.
<code style="display:inline-block">
'''function''' merge(a, b : '''Heap'''):
'''for''' i = 0 '''to''' b.heapSize - 1
a.heapSize = a.heapSize + 1
a[a.heapSize - 1] = b[i]
a.heapify()
</code>
===Поиск k-ого элемента===
Требуется найти <tex>k</tex>-ый по величине элемент в куче.
# Создаем новую кучу, в которой будем хранить пару <tex>\langle \mathtt{value}, \mathtt{index} \rangle</tex>, где <tex>\mathtt{value}</tex> {{---}} значение элемента, а <tex>\mathtt{index}</tex> {{---}} индекс элемента в основном массиве, и добавляем в нее корень кучи.
# Возьмем корень новой кучи и добавим её детей из основной кучи, после чего удалим корень. Проделаем этот шаг <tex>k - 1</tex> раз.
# В корне новой кучи будет находиться ответ.
Время работы алгоритма {{---}} <tex>O(k \log k)</tex>.
При <tex>n \lessapprox k \log k </tex> выгоднее запускать [[поиск k-ой порядковой статистики]].
[[Файл:Min_heap_kth.png|thumb|center|650px|Пример при <tex>k = 5</tex>, красные {{---}} уже удаленные из кучи элементы, зеленые находятся в куче, а голубые {{---}} еще не рассмотрены.]]
== См. также ==
* [[Фибоначчиева куча]]
* [[Левосторонняя куча]]
== Источники информации ==
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Приоритетные очереди]]
[[Категория: Структуры данных]]
