最小削除操作ではバイナリ ヒープが高速であり、優先度を下げる操作では d-ary ヒープが高速であることを読みました (理由はわかりませんが)。どちらもバイナリヒープと比較されます。
では、いつバイナリ ヒープを使用し、いつ D-ary ヒープを使用するのでしょうか? また、d-ary ヒープの d を決定するにはどうすればよいですか?
3608 次
2 に答える
7
ここには、いくつかの異なる要因が作用しているため、あなたの発言がすべて真実である可能性があると私は信じています.
これがなぜなのかを理解するために、d-ary ヒープの減少キーがどのように機能するかを考えることから始めましょう (バイナリ ヒープは単なる 2-ary ヒープであるため、バイナリ ヒープについて個別に説明する必要はありません)。キーの減少を実行する場合、ツリー内のノードの優先度を変更し、ツリーのルートに到達するか、その優先度が親の優先度よりも小さくなるまで、ノードをその親と繰り返しスワップします。スワップを行わなければならない回数は、最悪の場合、d-ary ヒープの高さによって決まります。d-ary ヒープの各層のノード数は、各ステップで d 倍に指数関数的に増加するため、d-ary ヒープの高さは O(log dn) = O(log n / log d)。これは、d の値を大きくすると、d-ary ヒープの高さが減少するため、キーの減少と挿入にかかる時間が短縮されることを意味します。極端な例を考えると、10 100配列のヒープがある場合、ツリーのレイヤー数はバイナリ ヒープの約 100 分の 1 になるため、キーの減少または挿入は約 100 倍速くなります。 .
一方、デキュー操作がどのように機能するかを考えてみてください。デキューを実行するには、最後のリーフをルートに交換し、次のことを繰り返します: 現在のノードのすべての子をスキャンし、それらのいずれかが現在のノードよりも小さい場合は、現在のノードをその子の中で最も小さい。これらの各反復では、最小の子を見つけるために合計 O(d) 回の比較が必要になります。反復の回数は、ツリー内のレイヤーの数によって決まります。これは、前に見た O(log n / log d) です。これは、d-ary ヒープでのデキューのコストが O(d log n / log d) であることを意味します。d は log d よりもはるかに速く (実際には指数関数的に) 大きくなるため、d を大きくすると、デキューの漸近的 (および実際の) コストが上昇し始めます。たとえば、10 100 では-ary ヒープでは、各ステップで各ノードを 10 100 の子と比較する必要がある場合があり、これには非常に長い時間がかかります! したがって、d-ary ヒープは、d が大きくなるにつれて、バイナリ ヒープよりもデキューが大幅に遅くなる傾向があります。
最後の質問に移りましょう: ここでの情報を考慮して、4 配列ヒープがバイナリ ヒープよりも優れている可能性があるのはなぜですか? 正直に言うと、これが本当かどうかはわかりませんが、(a) おそらくハードウェアに依存し、(b) 驚かないでしょう。これまでの分析はすべて、ヒープ内のレイヤー数や行われたスワップ数などの量を調べて、d-ary ヒープ操作のコストを制限しようとしたことに注意してください。ただし、これには、親と子を見つけるコストや参照の場所など、他の多くの要因が含まれていません。これらのうち最初のものについては、d-ary ヒープでは、インデックスを d で割ることによって親ノードを見つけることができることに注意してください。2 の完全べき乗である d の場合、これは単純な次のように実装できます。= n >> k)。奇数または 2 の累乗でない数の場合、これには除算が必要であり、(一部のアーキテクチャでは) ビット シフトよりもコストがかかります。さらに、参照の局所性の影響もあります。最近のコンピューターは、メモリ内に膨大な数のキャッシュ層を持っており、キャッシュ内のメモリにアクセスするコストは、キャッシュ内にないメモリにアクセスするコストよりも数百倍または数千倍高速になる可能性があります。d-ary ヒープの d の値を大きくすると、ツリー内のレイヤーが少なくなり、アクセスされる要素が近くなり、局所性が向上します。スイート スポットを見つけるには、おそらくいくつかの実験が必要です。たまたま d = 4 がマシンで最適である場合は、それを試してください。
編集: @moreON が指摘したように、d = 4 の場合、ヒープ内のレイヤーの数は 2 分の 1 に減少し、1 回あたりの比較回数は 2 分の 1 に増加します。これにより、実際には全体的なパフォーマンスが向上する可能性があります。効果をキャッシュし、全体的なツリーの高さを低くします。したがって、バイナリ ヒープよりもパフォーマンスが優れている可能性があります。
お役に立てれば！
于 2015-06-23T23:55:50.057 に答える