1632
правки
Изменения
м
<code style="display:inline-block">
</code>
rollbackEdits.php mass rollback
'''Двоичная куча''' или '''пирамида''' (англ. ''Binary heap'') — такое двоичное [[Дерево, эквивалентные определения|подвешенное дерево]], для которого выполнены следующие три условия:
* Значение в любой вершине не меньше больше (если куча для максимумаминимума), чем значения её потомков.
* На <tex>i</tex>-ом слое <tex>2^i</tex> вершин, кроме последнего. Слои нумеруются с нуля.
* Последний слой заполнен слева направо (как показано на рисунке)
# Сохранённый элемент возвращается.
'''int''' extractMin():
'''int''' min = a[0]
siftDown(0)
'''return''' min
===Добавление нового элемента===
{{Лемма
|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>
===Поиск k-ого элемента(очень коряво расписано с неверными индексами)===
Требуется найти <tex>k</tex>-ый по величине элемент в куче.
