Изменения
Нет описания правки
{{Определение
* Значение (ключ) в любой вершине не больше, чем значения её потомков.
* Каждый лист имеет глубину (расстояние до корня) либо <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'''(просеивание вниз) и '''Shift_Up'''(просеивание вверх). Если значение измененного элемента увеличивается, то свойства кучи восстанавливаются функцией '''Shift_Down(i)'''.
Работа процедуры : если <tex>i</tex>-й элемент больше, чем его сыновья, всё поддерево уже является кучей, и делать ничего не надо. В противном случае меняем местами <tex>i</tex>-й элемент с наибольшим из его сыновей, после чего выполняем '''Shift_Down(i)''' для этого сына.
Процедура выполняется за время <tex>O(logN)</tex>.
# Значение корневого элемента (он и является минимальным) сохраняется для последующего возврата.
# Последний элемент копируется в корень, после чего удаляется из кучи.
# Вызывается '''Shift_Down(i)''' для корня.
# Сохранённый элемент возвращается.
<code>
