Design-and-analysis-of-algorithms-insert-method
提供：Dev Guides
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） です。
例
以下に示すように、新しい要素5を追加する必要がある最大ヒープを考えてみましょう。
最初は、この配列の最後に55が追加されます。
挿入後、ヒーププロパティに違反します。 したがって、要素はその親と交換する必要があります。 スワップ後、ヒープは次のようになります。
繰り返しますが、この要素はヒープのプロパティに違反しています。 したがって、親と交換されます。
今、私たちは停止する必要があります。
