Двоичная куча

---

Двои́чная ку́ча, пирами́да^[1], или сортиру́ющее де́рево — такое двоичное дерево, для которого выполнены три условия:

Существуют также кучи, где значение в любой вершине, наоборот, не больше, чем значения её потомков. Такие кучи называются min-heap, а кучи, описанные выше — max-heap. В дальнейшем рассматриваются только max-heap. Все действия с min-heap осуществляются аналогично.

Удобная структура данных для сортирующего дерева — массив A, у которого первый элемент, A[1] — элемент в корне, а потомками элемента A[i] являются A[2i] и A[2i+1] (при нумерации элементов с первого). При нумерации элементов с нулевого, корневой элемент — A[0], а потомки элемента A[i] — A[2i+1] и A[2i+2]. При таком способе хранения условия 2 и 3 выполнены автоматически.

Высота кучи определяется как высота двоичного дерева. То есть она равна количеству рёбер в самом длинном простом пути, соединяющем корень кучи с одним из её листьев. Высота кучи есть ${\displaystyle \Theta \left(\log {N}\right)}$, где N — количество узлов дерева.

Здесь ${\displaystyle n}$ — количество элементов кучи. Пространственная сложность — ${\displaystyle O(1)}$ для всех вышеперечисленных операций и действий.

Подробное описание и алгоритмы этих действий и процедуры Heapify, необходимой для их выполнения, приведены в следующем разделе.

---