Учебники

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

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

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

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

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) 

Анализ

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

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

пример

Давайте рассмотрим максимальную кучу, как показано ниже, где необходимо добавить новый элемент 5.

Новый Элемент

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

массив

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

Своп

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

Перевернуто

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