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がこの配列の最後に追加されます。
挿入後、ヒーププロパティに違反します。したがって、要素はその親と交換する必要があります。スワップ後のヒープは次のようになります。
この場合も、要素はヒープのプロパティに違反します。したがって、親と交換されます。
今、私たちはやめなければなりません。