Изменения
→Извлечение минимального элемента: форматирование
'''Двоичная куча''' или '''пирамида''' (англ. ''Binary heap'') — такое двоичное [[Дерево, эквивалентные определения|подвешенное дерево]], для которого выполнены следующие три условия:
* Значение в любой вершине не меньше, больше (если куча для максимумаминимума), чем значения её потомков.
* На <tex>i</tex>-ом слое <tex>2^i</tex> вершин, кроме последнего. Слои нумеруются с нуля.
* Последний слой заполнен слева направо (как показано на рисунке)
Если в куче изменяется один из элементов, то она может перестать удовлетворять свойству упорядоченности. Для восстановления этого свойства служат процедуры <tex> \mathrm {siftDown} </tex> (просеивание вниз)
и <tex> \mathrm {siftUp} </tex> (просеивание вверх).
====siftDown====
Если значение измененного элемента увеличивается, то свойства кучи восстанавливаются функцией <tex> \mathrm {siftDown} </tex>.
Работа процедуры: если <tex>i</tex>-й элемент меньше, чем его сыновья, всё поддерево уже является кучей, и делать ничего не надо. В противном случае меняем местами <tex>i</tex>-й элемент с наименьшим из его сыновей, после чего выполняем <tex> \mathrm {siftDown} </tex> для этого сына.
Процедура выполняется за время <tex>O(\log{n})</tex>.
<code style="display:inline-block">
'''function''' siftDown(i : '''int'''):
'''while''' 2 * i + 1 <tex><</tex> a.heapSize <font color = "green">// heapSize {{---}} количество элементов в куче</font>
left = 2 * i + 1 <font color = "green">// left {{---}} левый сын</font>
right = 2 * i + 2 <font color = "green">// right {{---}} правый сын</font>
j = left
'''if''' right <tex><</tex> a.heapSize '''and''' a[right] <tex><</tex> Aa[left]
j = right
'''if''' a[i] <tex>\leqslant</tex> = a[j]
'''break'''
swap(a[i], a[j])
<code style="display:inline-block">
'''function''' siftUp(i : '''int'''):
'''while''' a[i] <tex><</tex> a[(i - 1) / 2] <font color = "green">// i <tex>==</tex> 0 {{---}} мы в корне</font>
swap(a[i], a[(i - 1) / 2])
i = (i - 1) / 2
# Сохранённый элемент возвращается.
'''int''' extractMin():
'''int''' min = a[0]
siftDown(0)
'''return''' min
===Добавление нового элемента===
Дан массив <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[2idi+1]...a[2idi+d]</tex>). Сделаем <tex> \mathrm {siftDown} </tex> для вершин, имеющих хотя бы одного потомка: от <tex dpi=140>\dfrac{n}{d}</tex> до <tex>0</tex>,{{---}} так как поддеревья, состоящие из одной вершины без потомков, уже упорядочены.
{{Лемма
|statement= На выходе получим искомую кучу.
|proof= При вызове До вызова <tex> \mathrm {siftDown} </tex> для вершины, ее поддеревья являются кучами. После выполнения <tex> \mathrm {siftDown} </tex> эта вершина с ее поддеревьями будут также являться кучей. Значит, после выполнения всех <tex> \mathrm {siftDown} </tex> получится куча.
}}
{{Лемма
Псевдокод алгоритма:
<code style="display:inline-block">
'''function''' heapifybuldHeap():
'''for''' i = a.heapSize / 2 '''downto''' 0
siftDown(i)
<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>
===Поиск k-ого элемента(очень коряво расписано с неверными индексами)===
Требуется найти <tex>k</tex>-ый по величине элемент в куче.
Время работы алгоритма {{---}} <tex>O(k \log k)</tex>.
При <tex>n \lnapprox lessapprox k \ log k</tex> выгоднее запускать [[поиск k-ой порядковой статистики]].
[[Файл:Min_heap_kth.png|thumb|center|650px|Пример при <tex>k = 5</tex>, красные {{---}} уже удаленные из кучи элементы, зеленые находятся в куче, а голубые {{---}} еще не рассмотрены.]]
