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

* Значение в любой вершине не меньше, (если куча для максимума), чем значения её потомков.
* На <tex>i</tex>-ом слое <tex>2^i</tex> вершин, кроме последнего. Слои нумеруются с нуля.
* Последний слой заполнен слева направо (как показано на рисунке)
}}
[[Файл:Min_heap.png‎|thumb|325px|Пример кучи для минимума]]
[[Файл:Min_heap_array.png‎|thumb|325px|Хранение кучи в массиве, красная стрелка {{---}} левый сын, зеленая {{---}} правый]]
Удобнее всего двоичную кучу хранить в виде массива <tex>a[0..n-1]</tex>, у которого нулевой элемент, <tex>a[0]</tex> — элемент в корне, а потомками элемента <tex>a[i]</tex> являются <tex>a[2i+1]</tex> и <tex>a[2i+2]</tex>. Высота кучи определяется как высота двоичного дерева. То есть она равна количеству рёбер в самом длинном простом пути, соединяющем корень кучи с одним из её листьев. Высота кучи есть <tex>O(\log{n})</tex>, где <tex>n</tex> — количество узлов дерева.

Чаще всего используют кучи для минимума (когда предок не больше детей) и для максимума (когда предок не меньше детей).

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

==Базовые процедуры==

===Восстановление свойств кучи===

Если в куче изменяется один из элементов, то она может перестать удовлетворять свойству упорядоченности. Для восстановления этого свойства служат процедуры <tex> \mathrm {siftDown} </tex> (просеивание вниз)
и <tex> \mathrm {siftUp} </tex> (просеивание вверх).
Если значение измененного элемента увеличивается, то свойства кучи восстанавливаются функцией <tex> \mathrm {siftDown} </tex>.
Работа процедуры: если <tex>i</tex>-й элемент меньше, чем его сыновья, всё поддерево уже является кучей, и делать ничего не надо. В противном случае меняем местами <tex>i</tex>-й элемент с наименьшим из его сыновей, после чего выполняем <tex> \mathrm {siftDown} </tex> для этого сына.
Процедура выполняется за время <tex>O(\log{n})</tex>.
====siftDown====
<code style="display:inline-block">
'''function''' siftDown(i : '''int'''):
'''while''' 2 * i + 1 <tex><</tex> a.heapSize // heapSize {{---}} количество элементов в куче
left = 2 * i + 1 // left {{---}} левый сын
right = 2 * i + 2 // right {{---}} правый сын
j = left
'''if''' right <tex><</tex> a.heapSize '''and''' a[right] <tex><</tex> A[left]
j = right
'''if''' a[i] <tex>\leqslant</tex> a[j]
'''break'''
swap(a[i], a[j])
i = j
</code>

====siftUp====
Если значение измененного элемента уменьшается, то свойства кучи восстанавливаются функцией <tex> \mathrm {siftUp} </tex>.

Работа процедуры: если элемент больше своего отца, условие 1 соблюдено для всего дерева, и больше ничего делать не нужно. Иначе, мы меняем местами его с отцом. После чего выполняем <tex> \mathrm {siftUp} </tex>
для этого отца. Иными словами, слишком маленький элемент всплывает наверх.
Процедура выполняется за время <tex>O(\log{n})</tex>.
<code style="display:inline-block">
'''function''' siftUp(i : '''int'''):
'''while''' a[i] <tex><</tex> a[(i - 1) / 2] // i <tex>==</tex> 0 {{---}} мы в корне
swap(a[i], a[(i - 1) / 2])
i = (i - 1) / 2
</code>

===Извлечение минимального элемента===

Выполняет извлечение минимального элемента из кучи за время <tex>O(\log{n})</tex>.
Извлечение выполняется в четыре этапа:
# Значение корневого элемента (он и является минимальным) сохраняется для последующего возврата.
# Последний элемент копируется в корень, после чего удаляется из кучи.
# Вызывается <math> \mathrm {siftDown} </math> для корня.
# Сохранённый элемент возвращается.

<code style="display:inline-block">
'''int''' extractMin():
'''int''' min = a[0]
a[0] = a[a.heapSize - 1]
a.heapSize = a.heapSize - 1
siftDown(0)
'''return''' min
</code>

===Добавление нового элемента===

Выполняет добавление элемента в кучу за время <tex>O(\log{n})</tex>.
Добавление произвольного элемента в конец кучи, и восстановление свойства упорядоченности с помощью процедуры <math> \mathrm {siftUp} </math>.

<code style="display:inline-block">
'''function''' insert(key : '''int'''):
a.heapSize = a.heapSize + 1
a[a.heapSize - 1] = key
siftUp(a.heapSize - 1)
</code>

==Построение кучи за O(n) ==
{{Определение | definition =
'''<tex>D</tex>-куча''' {{---}} это куча, в которой у каждого элемента, кроме, возможно, элементов на последнем уровне, ровно <tex>d</tex> потомков.
}}

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

Представим, что в массиве хранится дерево (<tex>a[0] - </tex> корень, а потомками элемента <tex>a[i]</tex> являются <tex>a[2i+1]...a[2i+d]</tex>). Сделаем <tex> \mathrm {siftDown} </tex> для вершин, имеющих хотя бы одного потомка: от <tex dpi=140>\genfrac {}{}{}{}{n}{d}</tex> до <tex>0</tex>,{{---}} так как поддеревья, состоящие из одной вершины без потомков, уже упорядочены.
{{Лемма
|statement= На выходе получим искомую кучу.
|proof= При вызове <tex> \mathrm {siftDown} </tex> для вершины, ее поддеревья являются кучами. После выполнения <tex> \mathrm {siftDown} </tex> эта вершина с ее поддеревьями будут также являться кучей. Значит, после выполнения всех <tex> \mathrm {siftDown} </tex> получится куча.
}}
{{Лемма
|statement= Время работы этого алгоритма <tex> O(n) </tex>.
|proof= Число вершин на высоте <tex>h</tex> в куче из <tex>n</tex> элементов не превосходит <tex dpi = "160"> \left \lceil \frac{n}{d^h} \right \rceil </tex>. Высота кучи не превосходит <tex> \log_{d}n </tex>. Обозначим за <tex> H </tex> высоту дерева, тогда время построения не превосходит

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

Докажем вспомогательную лемму о сумме ряда.

{{Лемма
|statement= <tex dpi = "160"> {\sum_{h = 1}^\infty \limits}\frac{h}{d^h} = \frac{d}{(d - 1)^2} . </tex>
|proof=
Обозначим за <tex>s</tex> сумму ряда. Заметим, что
<tex dpi = "160"> \frac{n}{d^n} = \frac{1}{d} \cdot \frac{n - 1}{d ^{n - 1}} + \frac{1}{d^n}. </tex>

<tex dpi = "160">{\sum_{n = 1}^\infty \limits}\frac{1}{d^n}</tex> {{---}} это сумма бесконечной убывающей геометрической прогрессии, и она равна <tex dpi = "160">
\frac{\frac{1}{d}}{1 - \frac{1}{d}} = \frac{1}{d - 1}. </tex>

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

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

==Слияние двух куч==
Даны две кучи <tex>a</tex> и <tex>b</tex>, требуется объединить эти две кучи.

Добавим все элементы кучи <tex>b</tex> в конец массива <tex>a</tex>, после чего вызовем функцию построения кучи. Процедура выполняется за время <tex>O(a.heapSize + b.heapSize)</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]
heapify(a)
</code>

==Поиск k-ого элемента==
Требуется найти <tex>k</tex>-ый по величине элемент в куче.

# Создаем новую кучу, в которой будем хранить пару <tex>\langle value, index \rangle</tex>, где <tex>value</tex> {{---}} значение элемента, а <tex>index</tex> {{---}} индекс элемента в основном массиве, и добавляем в нее корень кучи.
# Возьмем корень новой кучи и добавим её детей из основной кучи, после чего удалим корень. Проделаем этот шаг <tex>k - 1</tex> раз.
# В корне новой кучи будет находиться ответ.

[[Файл:Min_heap_kth.png‎|thumb|center|650px|Пример при <tex>k = 5</tex>, красные {{---}} уже удаленные из кучи элементы, зеленые находятся в куче, а голубые {{---}} еще не рассмотрены.]]

== См. также ==
* [[Биномиальная куча]]
* [[Фибоначчиева куча]]
* [[Левосторонняя куча]]

== Источники информации ==
* [[wikipedia:ru:Двоичная куча|Википедия {{---}} Двоичная куча]]
* [[wikipedia:ru:Очередь с приоритетом|Википедия {{---}} Очередь с приоритетом]]
* [[wikipedia:en:Binary heap|Wikipedia {{---}} Binary heap]]
* [[wikipedia:en:Priority queue|Wikipedia {{---}} Priority queue]]

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Приоритетные очереди]]

Файл:Min heap kth.png

2015-06-05T19:13:47Z

Ильнар:

Файл:Min heap array.png

2015-06-05T18:26:42Z

Ильнар:

2015-01-12T13:50:05Z

Ильнар:

{{Задача
|definition =
Пусть у нас есть отсортированный по возрастанию алфавит <tex>\Sigma = \{a_1, a_2, \cdots, a_n\}</tex>, <tex>|\Sigma| = n</tex>. Где <tex>a_i</tex> {{---}} число вхождений символа в строку.
Требуется построить код Хаффмана за <tex>O(n)</tex>.
}}

== Описание алгоритма ==

Eсли массив не отсортирован, то это можно сделать, например,[[Цифровая_сортировка | цифровой сортировкой]] за <tex> O(n) </tex>, что не ухудшит асимптотику.

Идея алгоритма заключается в том, чтобы создать такую [[Дискретная_математика,_алгоритмы_и_структуры_данных#.D0.9F.D1.80.D0.B8.D0.BE.D1.80.D0.B8.D1.82.D0.B5.D1.82.D0.BD.D1.8B.D0.B5_.D0.BE.D1.87.D0.B5.D1.80.D0.B5.D0.B4.D0.B8 | очередь с приоритетами]], из которой можно было бы доставать два минимума за <tex> O(1) </tex>, после чего в эту же очередь с приоритетами положить их сумму за <tex> O(1) </tex>. У нас уже есть массив с отсортированными частотами, теперь давайте заведем второй массив, в котором мы будем хранить суммы. Несложно заметить, что в этом массиве элементы тоже будут идти по неубыванию. Допустим, что на каком-то шаге сумма получилась меньше чем предыдущая, но это противоречит тому, что на каждом шаге мы выбираем два минимальных.
На каждой итерации мы будет выбирать два минимума из четырех элементов (первые 2 элемента первого массива и первые 2 элемента второго массива). Теперь рассмотрим одну итерацию подробнее.

У нас есть три варианта возможных пар минимумов :
# Оба элемента из первого массива.
# Первый элемент первого массива и первый элемент второго массива.
# Два первых элемента второго массива.

Во всех случаях мы дописываем сумму в конец второго массива и передвигаем указатели в массивах на еще не использованные элементы.

На каждом шаге количество элементов уменьшается ровно на один, а минимум из 4-х элементов мы выбираем за константное время, следовательно, программа делает ровно <tex>n</tex> итераций.

==Пример==
Для примера возьмем строку "абракадабра".
<tex>i, j</tex> {{---}} указатели на первые неиспользованные элементы в массиве 1 и 2, соответственно.

<tex>i = 0, j = 0</tex>
{| class="wikitable"
! Буква || д || к || б || р || а
|-
| Массив 1 || 1 || 1 || 2 || 2 || 5
|}
{| class="wikitable"
! || || || || ||
|-
| Массив 2 || <tex>\infty</tex> || <tex>\infty</tex> || <tex>\infty</tex> || <tex>\infty</tex> || <tex>\infty</tex>
|}

На первом шаге два минимальных элемента - это первые две ячейки первого массива. Их сумму сохраняем во второй массив.

<tex>i = 2, j = 0</tex>
{| class="wikitable"
! Буква || д || к || б || р || а
|-
| Массив 1 || 1|| 1 || 2 || 2 || 5
|}
{| class="wikitable"
! || дк || || || ||
|-
| Массив 2 || 2 || <tex>\infty</tex> || <tex>\infty</tex> || <tex>\infty</tex> || <tex>\infty</tex>
|}

На втором шаге снова суммируются первые две ячейки первого массива(нам все равно что взять, первый элемент второго массива или второй элемент первого).

<tex>i = 4, j = 0</tex>
{| class="wikitable"
! Буква || д || к || б || р || а
|-
| Массив 1 || 1|| 1 || 2 || 2 || 5
|}
{| class="wikitable"
! || дк || бр || || ||
|-
| Массив 2 || 2 || 4 || <tex>\infty</tex> || <tex>\infty</tex> || <tex>\infty</tex>
|}

На третьем шаге два минимальных элемента - это первые две ячейки второго массива.

<tex>i = 4, j = 2</tex>
{| class="wikitable"
! Буква || д || к || б || р || а
|-
| Массив 1 || 1 || 1|| 2|| 2|| 5
|}
{| class="wikitable"
! || дк || бр || дкбр || ||
|-
| Массив 2 || 2|| 4|| 6 || <tex>\infty</tex> || <tex>\infty</tex>
|}

На четвертом шаге складываются две оставшиеся ячейки.

<tex> i = 5, j = 3</tex>
{| class="wikitable"
! Буква || д || к || б || р || а
|-
| Массив 1 || 1 || 1 || 2 || 2 || 5
|}
{| class="wikitable"
! || дк || бр || дкбр || адкбр ||
|-
| Массив 2 || 2 || 4 || 6 || 11 || <tex>\infty</tex>
|}