Куча — это особый случай сбалансированной структуры данных бинарного дерева, где ключ корневого узла сравнивается с его дочерними элементами и распределяется соответствующим образом. Если α имеет дочерний узел β, то —
ключ (α) ≥ ключ (β)
Поскольку значение parent больше значения child, это свойство генерирует Max Heap . Исходя из этого критерия, куча может быть двух типов:
For Input → 35 33 42 10 14 19 27 44 26 31
Min-Heap — где значение корневого узла меньше или равно одному из его дочерних элементов.
Max-Heap — где значение корневого узла больше или равно одному из его дочерних узлов.
Оба дерева построены с использованием одинакового ввода и порядка прибытия.
Алгоритм построения Max Heap
Мы будем использовать тот же пример, чтобы продемонстрировать, как создается Max Heap. Процедура создания Min Heap похожа, но мы используем минимальные значения вместо максимальных.
Мы собираемся вывести алгоритм для максимальной кучи, вставляя по одному элементу за раз. В любой момент времени куча должна сохранять свою собственность. При вставке мы также предполагаем, что мы вставляем узел в уже кучи дерева.
Step 1 − Create a new node at the end of heap. Step 2 − Assign new value to the node. Step 3 − Compare the value of this child node with its parent. Step 4 − If value of parent is less than child, then swap them. Step 5 − Repeat step 3 & 4 until Heap property holds.
Примечание. В алгоритме построения Min Heap мы ожидаем, что значение родительского узла будет меньше значения дочернего узла.
Давайте разберемся с конструкцией Max Heap по анимированной иллюстрации. Мы рассматриваем ту же исходную выборку, которую использовали ранее.
Макс. Алгоритм удаления кучи
Давайте выведем алгоритм удаления из максимальной кучи. Удаление в Max (или Min) Heap всегда происходит в корне, чтобы удалить максимальное (или минимальное) значение.