B-heap
B-ヒープがあるバイナリヒープ単一でサブツリーを保つために実装ページ。これにより、従来の実装と比較して、仮想メモリを使用する場合に、大きなヒープでアクセスされるページ数が最大10分の1に削減されます。配列内の場所への要素の従来のマッピングでは、ほぼすべてのレベルが異なるページに配置されます。
キャッシュを意識しないアルゴリズム、kヒープ、、van Emde Boasレイアウトなど、仮想メモリまたはキャッシュを使用するコンピューターで効率的な他のヒープバリアントが
コンテンツ
1 動機
2 実装
2.1 親関数
3 も参照してください
4 参考文献
5 外部リンク
動機
従来、二分木はn -> {2n， 2n+1}規則に従って連続したメモリに配置されていました。つまり、ノードが位置nにある場合、その左右の子は位置2nと2n+1配列内にあると見なされます。ルートは位置1に二分木の一般的な操作は垂直走査です。検索されたノードに到達するために、ツリーのレベルをステップダウンします。ただし、最近のコンピュータではメモリが仮想メモリ内のページに編成される方法のため、バイナリツリーをレイアウトするこのスキームは非常に効果がない可能性がその理由は、ツリーの奥深くを移動すると、次のノードまでの距離が指数関数的に増加するため、取得される次のノードはすべて別のメモリページにある可能性が高いためです。これにより、非常に高価なページミス。Bヒープは、子ノードを異なる方法でメモリに配置し、単一ページ内にサブツリーをできるだけ配置しようとすることで、この問題を解決します。したがって、垂直トラバーサルが進むにつれて、連続して取得されたノードのいくつかが同じページに配置され、ページミスの数が少なくなります。
実装
詳細には、bヒープは次の方法で実装できます。Poul-Henning Kamp は、ノードのレイアウトに2つのオプションを提供します。1つはページごとに2つの位置が無駄になりますが、ツリーの厳密なバイナリ構造は保持され、もう1つはページの使用可能なスペース全体を使用します。ただし、新しいページに入ると、ツリーが1つのレベルで拡張できません（そのレベルのノードには子が1つしかありません）。いずれにせよ、重要な点は、ページを離れるとき、両方の子ノードが常に共通の他のページにあることです。垂直横断では、アルゴリズムは通常、両方の子を親と比較して、続行する方法を知るためです。このため、各ページには、互いに散在する2つの並列サブツリーが含まれていると言えます。ページ自体はm-aryツリーと見なすことができ、各ページの要素の半分が（ページ内の）葉になるため、「ページのツリー」の分割係数はpagesize/2。になります。
親関数
従来の配列のようなレイアウトとは対照的に、ノードの親のインデックスはページ内のどこにあるかによって異なる方法で計算する必要があるため、Bヒープの親関数はより複雑です。ページ内の位置に0からまでのラベルが付けられているとするpagesizeと、親関数は次のようになります。
ノード0および1の場合、これらはすべての可能なスペースを利用しているバリアントでのみ使用されます。この場合、両方のノードの親インデックスは同じであり、別のページにあり、そのページ内の特定のオフセットは現在のページ番号にのみ依存します。具体的には、親のページ番号を計算するには、現在のノードのページ番号を「ページツリー」の分割係数であるで除算するだけですpagesize/2。ページ内で正しいオフセットを取得するには、それが親ページ内のリーフノードの1つである必要があることを考慮して、offsetから開始しpagesize/2ます。次に、現在のページ番号と親のページ番号の差から、親ページの後の最初のページのインデックス（pagesize/2）に親ノードがあるため1を引いたものを追加します。
ノード2と3の場合、親はモードによって異なります。省スペースモードでは、親はそれぞれノード0と1であるため、2で減算するだけで済みます。一方、strict-binary-tree-modeでは、これらのノードがページのルートになります。 0と1の場合、それらの共通の親は上記と同じ方法で計算されます。
他のすべてのノードの場合、それらの親は同じページ内にあり、ページ番号を変更せずに、ページ内のオフセットを2で割るだけで十分です。
も参照してください
D-aryヒープ
参考文献
^ カンプ、ポールヘニング（2020-07-26）。「あなたはそれを間違ってやっている」。ACMキュー。
^ ナオール、ダリット; マーテル、チャールズU。; マトロフ、ノーマンS.（1991）。「仮想メモリ環境での優先キュー構造のパフォーマンス」。計算します。J. 34（5）：428–437。土井：10.1093 / comjnl /34.5.428。
^ van Emde Boas、P .; Kaas、R。; Zijlstra、E。（1976）。「効率的な優先キューの設計と実装」。数学システム理論。10：99〜127。土井：10.1007 / BF01683268。S2CID 8105468。 ^ phk.freebsd.dkhttp ：//phk.freebsd.dk/B-Heap/ 。
外部リンク
https://github.com/varnish/Varnish-Cache/blob/master/lib/libvarnish/binary_heap.cおよびhttp://phk.freebsd.dk/B-Heap/binheap.cでの実装
Bヒープをサポートする汎用ヒープの実装。
van Emde Boasレイアウトの詳細については、Benjamin Sach Descent intoCache -OblivionまたはCache-obliviousデータ構造を参照して