[解決済み] ヒープの構築はどうして時間計算量O(n)になるのですか？

質問

どなたか、ヒープを構築することがどのように可能か説明してください。 O(n) 複雑なのでしょうか？

ヒープにアイテムを挿入するのは O(log n) そして、挿入はn/2回繰り返されます（残りは葉であり、ヒープの性質に違反することはできません）。ということは、複雑さは O(n log n) と思いますね。

言い換えれば、各項目を "heapify"するごとに、これまでのヒープに対して各レベルで1回ずつフィルタリング（＝ふるい落とし）しなければならない可能性を持っています（つまり、これは ログN レベル)。

何が足りないのでしょうか？

解決方法は？

このトピックには、いくつかの質問が埋まっていると思います。

• をどのように実装するのですか？ buildHeap で実行されるように O(n) 時間？
• をどのように示すのですか？ buildHeap で実行されます。 O(n) の時間は、正しく実装されていますか？
• なぜ同じロジックで、ヒープソートの実行時間を O(n) 時間ではなく O(n log n) ?

をどのように実装するのですか？ buildHeap で実行されるように O(n) 時間？

多くの場合、これらの質問に対する回答は、以下の違いに焦点が当てられています。 siftUp と siftDown . のどちらかを正しく選択することです。 siftUp と siftDown を取得することが重要です。 O(n) のパフォーマンスを向上させます。 buildHeap との違いを理解する助けにはならない。 buildHeap そして heapSort が一般的です。実際 buildHeap と heapSort 意志 のみ 使用 siftDown . その siftUp 操作は、既存のヒープへの挿入を実行するためにのみ必要です。したがって、例えばバイナリヒープを使用してプライオリティキューを実装するために使用されるでしょう。

maxヒープの仕組みを説明するために書きました。これはヒープソートや優先度キューによく使われるタイプのヒープで、値が大きいほど優先度が高いことを示します。たとえば、整数のキーを持つアイテムを昇順で取得したり、文字列をアルファベット順に取得したりするときに、min ヒープも役に立ちます。原理は全く同じで、単にソート順を入れ替えるだけです。

その ヒーププロパティ は、バイナリヒープの各ノードが、少なくともその子の両方と同じ大きさでなければならないことを規定しています。特に、これはヒープ内の最大のアイテムがルートにあることを意味する。ふるい落とすこととふるい上げることは、基本的に同じ操作で、方向が逆である。つまり、ヒープ特性を満たすまで問題のあるノードを移動させる。

• siftDown は、小さすぎるノードを、その下にある両方のノードと同じ大きさになるまで、最大の子ノードと交換します（それによって、ノードは下に移動します）。
• siftUp 大きすぎるノードを、その上のノードより大きくなくなるまで親ノードと交換する（それによって上に移動する）。

に必要な操作回数 siftDown と siftUp はノードの移動距離に比例する。の場合 siftDown の場合、それはツリーの底までの距離なので siftDown は、ツリーの先頭にあるノードに対して高価である。とは siftUp の場合、作業は木の頂点までの距離に比例するので siftUp は、木の最下部にあるノードに対して高価である。どちらの操作も O(log n) ヒープでは、最悪の場合、一番上にあるノードは1つだけで、半分のノードは一番下の層にあることになります。そこで もし、すべてのノードに操作を適用しなければならないのであれば、私たちがこのような操作を好むのはそれほど驚くことではありません。 siftDown オーバー siftUp .

は buildHeap 関数は、ソートされていない項目の配列を受け取り、それらがすべてヒーププロパティを満たすまで移動し、それによって有効なヒープを生成します。この関数には2つのアプローチがあります。 buildHeap を使用しています。 siftUp と siftDown の操作を説明しました。

1. ヒープの先頭（配列の先頭）から始めて siftUp を各アイテムに対して実行する。各ステップにおいて、前にふるい分けられたアイテム（配列の現在のアイテムより前のアイテム）は有効なヒープを形成し、次のアイテムをふるい分けるとヒープ内の有効な位置に配置されます。各ノードをふるい落とした後、すべてのアイテムはヒープ特性を満たす。

2. また、逆に配列の末尾から先頭に向かって後退させることもできます。各反復で、アイテムが正しい位置に来るまで下にふるい落とすのです。

の実装は？ buildHeap はより効率的ですか？

これらの解決策は両方とも有効なヒープを生成します。当然のことながら、より効率的なのは、2番目の操作で siftDown .

Let h = log n はヒープの高さを表します。に必要な作業は siftDown の和で与えられる。

(0 * n/2) + (1 * n/4) + (2 * n/8) + ... + (h * 1).

和の各項は、与えられた高さのノードが移動しなければならない最大距離（最下層は0、ルートはh）に、その高さのノードの数を掛けたものである。これに対して siftUp は、各ノードに対して

(h * n/2) + ((h-1) * n/4) + ((h-2)*n/8) + ... + (0 * 1).

2番目の合計の方が大きいことは明らかでしょう。第1項だけでは hn/2 = 1/2 n log n したがって、このアプローチはせいぜい複雑である O(n log n) .

の和はどのように証明するのでしょうか？ siftDown のアプローチは、確かに O(n) ?

有限和を無限級数にして、テイラー級数を使うのも一つの方法です（他にも有効な解析があります）。初項は0なので無視してもよい。

もし、これらの各ステップがなぜ機能するのかよくわからない場合は、ここにプロセスの正当性を言葉で説明します。

• 項はすべて正なので、有限和は無限和より小さくなければならない。
• で評価される冪級数と等しい。 x=1/2 .
• のテイラー級数の微分に等しい（定数倍）。 f(x)=1/(1-x) .
• x=1/2 は、そのテイラー級数の収束区間内である。
• したがって、テイラー級数を次のように置き換えることができます。 1/(1-x) を微分して評価し、無限級数の値を求めます。

無限和は正確に n であることから、有限和はこれより大きくないと結論づけられる。 O(n) .

なぜヒープソートには O(n log n) 時間？

を実行することが可能であれば buildHeap が必要なのはなぜですか？ O(n log n) 時間？さて、ヒープソートは2つのステージから構成されています。まず buildHeap を配列に適用する必要があり、そのためには O(n) を最適に実装する必要があります。次の段階は、ヒープ内の最大の項目を削除して配列の末尾に置くことを繰り返すことです。ヒープから項目を削除するので、ヒープの終端直後には常に項目を格納できる空き領域が存在します。つまり、ヒープソートは、最後の位置から前方に向かって、次に大きな項目を削除して配列に入れることを繰り返すことで、ソート順を実現しているのです。ヒープソートで支配的なのは、この最後の部分の複雑さである。ループは次のようなものです。

for (i = n - 1; i > 0; i--) {
    arr[i] = deleteMax();
}

明らかに、このループはO(n)回実行されます ( n - 1 正確には、最後の項目が既にある)。の複雑さは deleteMax ヒープに対して O(log n) . 通常、ルート (ヒープに残っている最大のアイテム) を取り除き、ヒープの最後のアイテム (リーフ) で置き換えることで実装されます。この新しいルートは、ほぼ確実にヒープ・プロパティに違反するため siftDown それを許容できる位置に戻すまで。これは、次に大きいものをルートに移動させる効果もある。とは対照的に buildHeap ここでは、ほとんどのノードで siftDown をツリーの一番下から呼び出すようにしました。 siftDown をツリーの先頭から繰り返し実行します。 ツリーは縮小していくが、そのスピードは十分ではない : ツリーの高さは、最初の半分のノードを削除するまで（最下層を完全にクリアするまで）一定に保たれます。そして、次の4分の1は、高さが h - 1 . つまり、この第2ステージの総仕事は

h*n/2 + (h-1)*n/4 + ... + 0 * 1.

このスイッチに注目してください：今、ゼロの仕事のケースは1つのノードに対応し h は、半分のノードに対応します。この和は O(n log n) の非効率版と同じように buildHeap は、siftUp を使って実装されています。しかし、この場合、ソートしようとしているため、選択の余地はありませんし、次に大きい項目が次に削除されることを要求しています。

まとめると、ヒープソートの作業は2つのステージの合計となる。 buildHeapにO(n)時間、そして 各ノードを順番に削除するのにO(n log n) したがって、複雑さはO(n log n)です。 . 比較ベースのソートでは、（情報理論からのいくつかのアイデアを使って）次のように証明することができます。 O(n log n) は、いずれにしても期待できる最高のものです。ですから、このことに失望したり、ヒープソートで buildHeap ということです。