なぜヒープのdeleteMinにO（logn）が必要ですか？

Question

私のクラスの講義スライドにはヒープがあり、deleteMin（）というメソッドがあります。 これは、ヒープの最小値を削除します。そしてそれはO（logn）が必要だと言います。

これはわかりません。 ヒープ構造では、ヒープが "Upheap"と "Downheap"と呼ばれる操作を行うため、最小値は常にツリーのルートにあります。子ノードが親ノードの値よりも小さい場合、常に親ノードとスワップします。これは、ツリーのルートが常に最小値を持つことを意味します。私は、最小値を見つけて削除するときにその値を取ることができると思います。これはO（1）だけです。

しかし、なぜO（logn）と表示されますか？

Answer 1

トップノードを取り出した場合は、残りの2つのヒープを1つのヒープに改造する必要があるためです。ヒープのプロパティを保持するには、一番下の行の一番右の要素をルートにし、次に降下する必要があります。これにはO（log n）が必要です。私はあなたがこれを達成するより良い方法を検討していると思うが、上記の方法は現在、最速の方法です。この投稿があなたを助けてくれることを祈っています