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