Двоичная куча (binary heap)
Структуры данных:
двоичная куча (binary heap)
Двоичная куча (binary heap) – просто реализуемая структура данных, позволяющая быстро (за логарифмическое время) добавлять элементы и извлекать элемент с максимальным приоритетом (например, максимальный по значению).
Добавление элемента
Новый элемент добавляется на последнее место в массиве, то есть позицию с индексом heapSize. Cледует «поднимать» новый элемент на один уровень (менять с вершиной-родителем) до тех пор, пока не будет соблюдено основное свойство кучи
Извлечение (удаление) максимального элемента
В упорядоченном max-heap максимальный элемент всегда хранится в корне. Восстановить упорядоченность двоичной кучи после удаления максимального элемента можно, поставив на его место последний элемент и вызвав балансировку через обмен с меньшим листом для корня, то есть упорядочив все дерево.
Операция балансировки приведена ниже:
