DAA-挿入メソッド

ヒープに要素を挿入するために、新しい要素は最初に配列の最後の要素としてヒープの最後に追加されます。

この要素を挿入した後、ヒーププロパティに違反する可能性があるため、追加された要素をその親と比較し、追加された要素を1レベル上に移動して、親と位置を入れ替えることにより、ヒーププロパティが修復されます。このプロセスは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)

以下に示すように、新しい要素5を追加する必要がある最大ヒープについて考えてみましょう。

最初に、55がこの配列の最後に追加されます。

挿入後、ヒーププロパティに違反します。したがって、要素はその親と交換する必要があります。スワップ後のヒープは次のようになります。

この場合も、要素はヒープのプロパティに違反します。したがって、親と交換されます。

今、私たちはやめなければなりません。