Изменения
Нет описания правки
'''Двоичная куча''' или '''пирамида''' — такое двоичное дерево, для которого выполнены три условия:
* Значение (ключ) в любой вершине не меньшебольше, чем значения её потомков.
* Каждый лист имеет глубину (расстояние до корня) либо <tex>d</tex> либо <tex>d-1</tex>. Иными словами, если назвать слоем совокупность вершин, находящихся на определённой глубине, то все слои, кроме, быть может, последнего, заполнены полностью.
===Восстановление свойств кучи===
Если в куче изменяется один из элементов, то она может перестать удовлетворять свойству упорядоченности. Для восстановления этого свойства служит процедура служат процедуры '''Shift_Down'''(просеивание вниз). Она восстанавливает свойство кучи в дереве, у которого левое и правое поддеревья удовлетворяют ему'''Shift_Up'''(просеивание вверх). Эта процедура принимает на вход массив элементов <tex>A</tex> и индекс <tex>i</tex>. Она восстанавливает свойство упорядоченности во всём поддеревеЕсли значение измененного элемента увеличивается, корнем которого является элемент <tex>A[то свойства кучи восстанавливаются функцией '''Shift_Down(i]</tex>)'''.Если Работа процедуры : если <tex>i</tex>-й элемент больше, чем его сыновья, всё поддерево уже является кучей, и делать ничего не надо. В противном случае меняем местами <tex>i</tex>-й элемент с наибольшим из его сыновей, после чего выполняем '''Shift_Down''' для этого сына.
Процедура выполняется за время <tex>O(logN)</tex>.
min = i
If (min <> i)
Shift_Down(A, min)
</code>
Если значение измененного элемента уменьшается, то свойства кучи восстанавливаются функцией'''Shift_Up(i)'''.
Работа процедуры : если элемент больше своего отца, условие 1 соблюдено для всего дерева, и больше ничего делать не нужно. Иначе, мы меняем местами его с отцом. После чего выполняем '''Shift_Up''' для этого отца. Иными словами, слишком большой элемент всплывает наверх.
Процедура выполняется за время <tex>O(logN)</tex>.
<code>
Shift_Up(i)
If (A[i] < A[i / 2])
Поменять A[i] и A[i / 2]
Shift_Up(i / 2)
</code>
A[1] = A[A.heap_size]
A.heap_size = A.heap_size - 1
Shift_Down(A, 1)
return min
</code>
===Добавление нового элемента===
== Источники ==
* [http://ru.wikipedia.org/wiki/Min-heap Двоичная куча]
