Изменения
Нет описания правки
'''Двоичная куча''' или '''пирамида''' — такое двоичное дерево, для которого выполнены три условия:
* Значение (ключ) в любой вершине не меньше, чем значения её потомков.
* Каждый лист имеет глубину (расстояние до корня) либо <tex>d </tex> либо <tex>d-1</tex>. Иными словами, если назвать слоем совокупность вершин, находящихся на определённой глубине, то все слои, кроме, быть может, последнего, заполнены полностью.
* Последний слой заполняется слева направо.
}}
Удобная структура данных для сортирующего дерева — массив <tex>A</tex>, у которого первый элемент, <tex>A[1]</tex> — элемент в корне, а потомками элемента <tex>A[i]</tex> являются <tex>A[2i]</tex> и <tex>A[2i+1]</tex>. Высота кучи определяется как высота двоичного дерева. То есть она равна количеству рёбер в самом длинном простом пути, соединяющем корень кучи с одним из её листьев. Высота кучи есть <tex>O(logN)</tex>, где <tex>N</tex> — количество узлов дерева.
==Базовые процедуры==
===Восстановление свойств кучи===
Если в куче изменяется один из элементов, то она может перестать удовлетворять свойству упорядоченности. Для восстановления этого свойства служит процедура '''Shift_Down'''(просеивание вниз). Она восстанавливает свойство кучи в дереве, у которого левое и правое поддеревья удовлетворяют ему. Эта процедура принимает на вход массив элементов <tex>A</tex> и индекс <tex>i</tex>. Она восстанавливает свойство упорядоченности во всём поддереве, корнем которого является элемент <tex>A[i]</tex>.
Если <tex>i</tex>-й элемент больше, чем его сыновья, всё поддерево уже является кучей, и делать ничего не надо. В противном случае меняем местами <tex>i</tex>-й элемент с наибольшим из его сыновей, после чего выполняем '''Shift_Down''' для этого сына.
Процедура выполняется за время <tex>O(logN)</tex>.
<code>
Shift_Down(i)
left = 2 * i // левый сын
right = 2 * i + 1 // правый сын
// heap_size - количество элементов в куче
If (left ≤ A.heap_size) and (A[left] < A[i])
min = left
else
min = i
If (right ≤ A.heap_size) and (A[right] < A[i])
min = right
else
min = i
If (min <> i)
Обменять A[i] и A[largest]
Shift_Down(A, min)
</code>
===Изменение значения элемента===
После изменения <tex>i</tex>-ого элемента вызывается функция Shift_Up, которая просеивает
===Извлечение минимального элемента===
Выполняет извлечение минимального элемента из кучи за время <tex>O(logN)</tex>.
Извлечение выполняется в четыре этапа:
# Значение корневого элемента (он и является минимальным) сохраняется для последующего возврата.
# Последний элемент копируется в корень, после чего удаляется из кучи.
# Вызывается '''Shift_Down''' для корня.
# Сохранённый элемент возвращается.
<code>
extract_min()
min = A[1]
A[1] = A[A.heap_size]
A.heap_size = A.heap_size - 1
Shift_Down(A, 1)
return min
</code>
===Добавление нового элемента===
Элемент добавляется в конец кучи
