63
правки
Изменения
Нет описания правки
==Определение==
{{Определение
|definition=
* Последний слой заполнен слева направо (как показано на рисунке)
}}
[[Файл:HeapMin_heap.pngpng|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>.
====siftDown====
<codestyle="display:inline-block">
'''function''' siftDown(i : '''int'''):
'''while''' 2 * i + 1 <tex><</tex> a.heapSize <font color = "green">// heapSize {{---}} количество элементов в куче</font>
для этого отца. Иными словами, слишком маленький элемент всплывает наверх.
Процедура выполняется за время <tex>O(\log{n})</tex>.
<codestyle="display:inline-block">
'''function''' siftUp(i : '''int'''):
'''while''' a[i] <tex><</tex> a[(i - 1) / 2] <font color = "green">// i <tex>==</tex> 0 {{---}} мы в корне</font>
# Сохранённый элемент возвращается.
<codestyle="display:inline-block">
'''int''' extractMin():
'''int''' min = a[0]
a[0] = a[Aa.heapSize - 1]
a.heapSize = a.heapSize - 1
siftDown(0)
Добавление произвольного элемента в конец кучи, и восстановление свойства упорядоченности с помощью процедуры <math> \mathrm {siftUp} </math>.
<codestyle="display:inline-block">
'''function''' insert(key : '''int'''):
a.heapSize = a.heapSize + 1
Добавим все элементы кучи <tex>b</tex> в конец массива <tex>a</tex>, после чего вызовем функцию построения кучи. Процедура выполняется за время <tex>O(a.heapSize + b.heapSize)</tex>.
<codestyle="display:inline-block">
'''function''' merge(a, b : '''heap'''):
'''for''' i = 0 '''to''' b.heapSize - 1
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>, красные {{---}} уже удаленные из кучи элементы, зеленые находятся в куче, а голубые {{---}} еще не рассмотрены.]]
== См. также ==
