Операции с Heap

Рассмотрим некоторые из важных операций, выполняемых с кучей, и их алгоритмы.

Нагромождение

Heapify — это процесс создания структуры данных кучи из двоичного дерева. Он используется для создания Min Heap или Max Heap.

1. Пусть входной массив будет таким.

1. Создай полное бинарное дерево из массива.

1. Начни с первого индекса нелистового узла, индекс которого задается n/2 - 1.

1. Установи текущий элемент i как largest.

2. Индекс левого дочернего элемента определяется как 2i + 1а, правого дочернего элемента — как 2i + 2.

Если rightChild больше, чем элемент в largest, установи rightChildIndex как largest.

Поменяй местами largest с currentElement.

1. Если leftChild больше, чем currentElement (т. е. элемент по ith индексу), установи leftChildIndex как самый большой.

1. Повторяй шаги 3–7, пока поддеревья также не будут загружены.

Алгоритм heapify (псевдокод)

Чтобы создать Max-Heap (псевдокод):

Для Min Heap оба leftChild и rightChild должны быть больше, чем родитель для всех узлов.

Вставка элемента в кучу

Алгоритм вставки в Max Heap (псевдокода):

1. Вставь новый элемент в конец дерева.

1. Произведи алгоритм heapify.

Для Min Heap приведенный выше алгоритм изменен таким образом, что parentNode всегда меньше newNode.

Удаление элемента из кучи

Алгоритм удаления в Max Heap

1. Выбери элемент, который необходимо удалить.

1. Поменяй его местами с последним элементом.

1. Удали последний элемент.

1. Результат после heapify.

Для Min Heap приведенный выше алгоритм изменен так, что оба значения childNodes меньше, чем currentNode.

Peek (найти макс./мин.)

Операция просмотра возвращает максимальный элемент из максимальной кучи или минимальный элемент из минимальной кучи без удаления узла.

Как для максимальной кучи, так и для минимальной кучи:

Извлечение-макс./мин.

Extract Max возвращает узел с максимальным значением после его удаления из максимальной кучи, тогда как Extract Min возвращает узел с минимальным значением после его удаления из минимальной кучи.