DAA - метод вставки

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

После вставки этого элемента свойство кучи может быть нарушено, поэтому свойство кучи восстанавливается путем сравнения добавленного элемента с его родительским элементом и перемещения добавленного элемента на уровень выше, меняя местами позиции с родительским элементом. Этот процесс называетсяpercolation up.

Сравнение повторяется до тех пор, пока родительский элемент не станет больше или равен перколяционному элементу.

Algorithm: Max-Heap-Insert (numbers[], key) 
heapsize = heapsize + 1 
numbers[heapsize] = -∞ 
i = heapsize 
numbers[i] = key 
while i > 1 and numbers[Parent(numbers[], i)] < numbers[i] 
   exchange(numbers[i], numbers[Parent(numbers[], i)]) 
   i = Parent (numbers[], i)

Анализ

Первоначально в конец массива добавляется элемент. Если он нарушает свойство кучи, элемент обменивается со своим родителем. Высота дереваlog n. Максимумlog n количество операций, которые необходимо выполнить.

Следовательно, сложность этой функции равна O(log n).

пример

Давайте рассмотрим max-heap, как показано ниже, куда нужно добавить новый элемент 5.

Первоначально 55 будет добавлено в конец этого массива.

После вставки это нарушает свойство кучи. Следовательно, элемент должен поменяться местами со своим родителем. После свопа куча выглядит следующим образом.

Опять же, элемент нарушает свойство heap. Следовательно, он заменяется своим родителем.

Теперь нам нужно остановиться.