抽出実行時間とは何ですか？なぜですか？

Question

ヒープ内の抽出-minにはなぜO（lg n）が必要ですか？

Answer 1

が参照してください：

• まず、最後のレベルの最後の要素をヒープの根を置き換える：https://en.wikipedia.org/wiki/Binary_heap#Extractいくつかの単語で

  、次の3つの手順を実行します。それはO（1）のために行われます。

• 次に、新しいルートとその子（まだO（1））を比較します。すべてが大丈夫なら、あなたは終わった！
• 今は面倒です。新しいルートが大きい場合（私たちは、あなたがその上の最小を持っていると考えています）、その1つの子供よりも、それらを交換してください！あなた（おそらく）は子供のサブツリーに同じ問題を抱えています。サブツリー内でステップ2と3を繰り返します。 ではなく、は1レベル下がるたびにツリーのレベル数よりもこの回数を繰り返さなければなりません。バランスのとれたバイナリツリーにはO（Ng N）レベルがあります。注：あなたのルートが両方の子供のそれよりも大きい場合は、小さいものと交換してください（あなたがそれを持ち出そうとしています）。