Структуры данных кучи

Куча - это особый случай сбалансированной структуры данных двоичного дерева, в которой ключ корневого узла сравнивается с его дочерними элементами и распределяется соответствующим образом. Если α имеет дочерний узел β, то -

ключ (α) ≥ ключ (β)

Поскольку значение parent больше значения child, это свойство генерирует Max Heap . Исходя из этого критерия, куча может быть двух типов:

For Input → 35 33 42 10 14 19 27 44 26 31

Min-Heap - где значение корневого узла меньше или равно одному из его дочерних элементов.

Пример Max Heap

Max-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 Heap Анимированный пример

Максимальный алгоритм удаления кучи

Давайте выведем алгоритм удаления из максимальной кучи. Удаление в Max (или Min) Heap всегда происходит в корне, чтобы удалить максимальное (или минимальное) значение.

 Step 1 − Remove root node.
Step 2 − Move the last element of last level to root.
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.
Max Heap Deletion Анимированный пример