弱いヒープ

コンピュータサイエンスにおいて、弱ヒープは、二項ヒープと二項ヒープの特徴を組み合わせた、優先度キュー用のデータ構造です。二項ヒープと同様に暗黙的な二分木として配列に格納でき、二項ヒープと同様の効率性を保証します。

弱いヒープを使用するソートアルゴリズムである weak-heapsort は、リストをソートするために必要な比較回数の理論上の下限に近い比較回数を使用するため、完全なUnicode 照合アルゴリズムを使用して文字列を比較する場合など、比較にかかるコストが高い場合に特に役立ちます。

説明

弱いヒープは、ヒープ順序付き多元木を「右子左兄弟」規則に従って二分木として格納したものとして理解するのが最も簡単です。（これは通常の左子右兄弟二分木と同等ですが、逆になっています。）

マルチウェイツリーでは、最大ヒープを想定すると、各親のキーはすべての子キー（したがって、帰納的にサブツリーのすべてのメンバー）以上（ $\geq ）になります。$

これを二分木で表現すると、次の不変量となる: ^[1]

ルートノードには左の子ノードがありません
すべてのノードについて、そのノードに関連付けられた値は、その右側のサブツリー内のすべてのノードに関連付けられた値以上になります。
木の葉の高さはすべて互いに同じ範囲内にあります。

最後の条件は、暗黙的な二分木が完全な二分木であるという事実の結果です。

この木の構造は、従来の $1$ ベース（アーネンターフェル）の暗黙的二分木構造に非常によく一致しています。つまり、ノード $kには、$ $2 k$ という番号の次の兄弟（左の子）と、 $2 k + 1$ という番号の最初の子（右の子）があり、さらに $0 という$ 番号のルートが追加されています。このルートには兄弟はなく、最初の子であるノード $1$ ( $2\times0 + 1$ ) のみがあります。

$この構造は二項ヒープの構造と非常に似ており、高さh$ の木は根と高さ $h - 1$ , $h - 2$ , ..., $1の木から構成されます。2$ $n$ 個の要素を持つ完全（欠落葉なし）弱ヒープは、同じサイズの $二$ 項ヒープと全く同型ですが^{[2] 、2つのアルゴリズムは} $2$ のべき乗ではないサイズの扱い方が異なります。二項ヒープは複数の完全木を使用するのに対し、弱ヒープは単一の不完全木を使用します。

弱いヒープは、ノードの左と右の子（および関連するサブツリー）を交換する機能を必要とします。ツリーの明示的（ポインタベース）表現では、これは簡単です。暗黙的（配列）表現では、どの子が左の子であるかを示すために、内部ノードごとに1つの「逆ビット」が必要です。したがって、弱いヒープは、 $O （ n ）$ の追加スペース（⁠1/2⁠ビット/ノード）。ただし、既に存在するポインタをタグ付けするなどして、ノード構造内にこの追加ビット用のスペースを見つけることが可能な場合がよくあります。

暗黙の二分木では、逆ビット $r$ $k$ $を持つノードk$ は親 $⌊$ $⁠$ $け / 2 ⁠ ⌋$ 、左の子 $2 k + r k$ 、右の子 $2 k + 1 - r k$ 。

多元木として見ると、弱ヒープ内の各ノードは「次の兄弟」と「最初の子」という2つの他のノードにリンクされています。暗黙的な木ではリンクは固定されているため、 2つのリンクのうちどちらが兄弟でどちらが最初の子であるかは、逆ビットによって示されます。

弱いヒープに対する操作

弱ヒープ内の各ノードは、次の兄弟ノードを無視することで、より小さな弱ヒープのルートと見なすことができることに注意してください。最初の子ノードを持たないノードは、自動的に有効な弱ヒープとなります。

$高さh$ のノードには $h - 1 個$ の子ノードがあります。最初の子ノードは高さ $h - 1$ 、2番目の子ノードは高さ $h - 2$ 、そして最後の子ノードは高さ $1$ です。これらの子ノードは、最初の子ノードのリンクをたどり、次に次の兄弟ノードのリンクをたどることで見つけることができます。

$また、高さh - 1$ 、 $h - 2$ などの次の兄弟も存在します。

多元木におけるノードの親は、「識別祖先」と呼ばれます。二分木でこれを見つけるには、ノードの二分親を探します。ノードが右の子（最初の子）である場合、親は識別祖先です。ノードが左の子（次の兄弟）である場合、その識別祖先は二分親の識別祖先と同じです。暗黙木では二分親を見つけるのは簡単ですが、ノードがどのタイプの子であるかを判断するには、その逆ビットを参照する必要があります。（初期の論文では、識別祖先を「祖父母」と呼んでいましたが、^[3]これは通常の「親の親」とは意味が異なり、紛らわしいです。）

識別された祖先はツリー内で $log 2 n$ レベル高い可能性がありますが、平均距離は $2$ です。(少なくとも $1$ であり、再帰の半分の時間で $D = 1 + D /2$ となり、つまり $D = 2$ となります。) したがって、識別された祖先を見つけるための単純な反復アルゴリズムでも十分です。

二項式ヒープと同様に、弱ヒープに対する基本的な操作は、高さ $hが等しい2つのヒープをマージして、高さ$ $h +1$ の弱ヒープを作成することです。これには、ルート間の比較が1回だけ必要になります。どちらか大きい方のルート（最大ヒープを想定）が最終的なルートになります。その最初の子は負けルートであり、負けルートの子（右部分木）は保持されます。勝ちルートの子は負けルートの兄弟としてインストールされます。

この操作は暗黙的な木構造に対して実行できます。なぜなら、マージされるヒープは任意のものではないからです。むしろ、2つのヒープは、多元木におけるノードのシフト処理の一部として形成されます。

1 つ目は、通常の弱いヒープです (次の兄弟リンクは存在しますが、無視されます)。
2 番目は、最初のルートの区別された祖先 (多元的親) を最初のルートの次の兄弟にリンクすることによって形成される仮想ヒープです。

ヒープ不変条件は、最初のルートとその祖先ノードの間を除いて、すべてのノードに適用されます。他のすべてのノードは、それぞれの祖先ノード以下です。

2 つのルートを比較した後、マージは次の 2 つの方法のいずれかで進行します。

(識別された祖先は、より大きいか、等しいです。) 何も移動する必要がなく、マージの結果は、識別された祖先になります。
(最初のルートの方が大きいです。) 最初のルートのバイナリチャイルド (最初の子と次の兄弟) が交換され (反転ビットを使用)、次に最初のルートとその区別された祖先が交換されます (コピーによって)。

2番目のケースは、多元木において各ノードが自身の子ノードを保持しているため、機能します。最初のルートは、その祖先ノードよりも大きいため、ツリーを上方に昇格します。したがって、ルートは祖先ノードのそれ以前のすべての子ノードよりも安全に大きくなります。

ただし、前の祖先は最初のルートより小さいため、そのすべての子以上であることが保証されていないため、最初のルートの古い子にとって安全な親ではありません。

バイナリの子を交換することで、降格した祖先の古い子（安全にそれ以下であるもの）の適切なサブセットが、それとともに降格されます。降格した祖先の新しい兄弟は、最初のルートの古い子で昇格したもので、昇格した最初のルートより安全にそれ以下です。

この操作の後、新しい識別された祖先とその識別された祖先の間で不変条件が維持されるかどうかは不明であるため、ルートに到達するまで操作が繰り返されます。

弱ヒープソート

弱いヒープは、従来のヒープソートと基本的に同じ方法で、配列をソートするために使用できます。^[3] まず、配列のすべての要素から弱いヒープが構築され、次にルートが最後の要素と繰り返し交換され、最後の要素が適切な場所にシフトされます。

$n$ 要素の弱いヒープは、 $n - 1 回の$ マージで形成できます。マージの順序は様々ですが、単純なボトムアップ実装では、配列の末尾から先頭に向かって各ノードをその識別された祖先とマージします。識別された祖先を見つけるのは、マージ対象のヒープのすべての親の逆ビットが初期状態（「逆ではない」）から変更されていないため、参照する必要がないため、簡素化されます。

ヒープソートと同様に、ソートする配列がCPUキャッシュよりも大きい場合、次のレベルに進む前に1つのレベルのすべてのサブツリーをマージするのではなく、同じサイズのサブツリーが2つ利用可能になったらすぐにマージするとパフォーマンスが向上します。^[4]

弱いヒープにおけるシフトダウンは、 $h = ⌈ log 2 n ⌉ 回$ の比較で実行できます。これは、バイナリヒープでは $2 log 2 n$ 回、または「ボトムアップヒープソート」バリアントでは $1.5 log 2 n 回$ です。これは「マージアップ」によって行われます。ルートをヒープの最後の要素と交換した後、ルートの最後の（高さ1）子を見つけます。これをルート（その識別された祖先）とマージすることで、グローバルルートに有効な高さ2のヒープが作成されます。次に、最後にマージされたノードの前の兄弟（バイナリ親）に戻り、再度マージします。ルートに到達するまでこれを繰り返します。ルートに到達すると、完全なツリーとして正しいものになります。

優先キュー操作

弱い最大ヒープでは、最大値はルートノードに関連付けられた値として (定数時間で) 見つかります。同様に、弱い最小ヒープでは、最小値はルートで見つかります。

バイナリヒープと同様に、弱いヒープは、挿入、最小削除、削除、キー減少などの優先キューデータ構造の一般的な操作を、操作ごとに対数時間でサポートできます。

シフトアップは、バイナリヒープと同じプロセスで行われます。新しいノードはリーフレベルに追加され、その識別された祖先と比較され、必要に応じて交換されます（マージ操作）。これは、交換が不要になるかルートに到達するまで繰り返されます。

弱いヒープ構造の変種では、フィボナッチヒープの時間に合わせて、一定の償却時間で挿入とキーの減少が可能です。^[2]

歴史と応用

弱ヒープはダットン（1993）によって、（バイナリヒープを使用する標準的なヒープソートとは異なり） $n個のアイテムを$ $n$ $log$ $2$ $n$ $+$ $O$ $（$ $n$ $）$ 回の比較のみでソートできる変種ヒープソートアルゴリズムの一部として導入されました。^[3]^[5]その後、より一般的に適用可能な優先キューデータ構造として研究されました。^[6]^[7]

参考文献

^ Edelkamp, Stefan (2011年5月26日)、Pieterse, Vreda; Black, Paul E. (編)、「weak-heap」、Dictionary of Algorithms and Data Structures 、 2015年12月1日閲覧。
^ ab Edelkamp, Stefan; Elmasry, Amr; Katajainen, Jyrki (2012年10月)、「弱ヒープデータ構造：その変種と応用」（PDF）、Journal of Discrete Algorithms、16 : 187– 205、CiteSeerX 10.1.1.455.1213、doi :10.1016/j.jda.2012.04.010、MR 2960353 。
^ abc ダットン、ロナルド・D. (1993)、「弱ヒープソート」、BIT、33 (3): 372– 381、doi :10.1007/bf01990520、S2CID 5387832 。
^ Bojesen, Jesper; Katajainen, Jyrki; Spork, Maz (2000). 「パフォーマンスエンジニアリングのケーススタディ：ヒープ構築」（PostScript） . ACM Journal of Experimental Algorithmics . 5 (15). CiteSeerX 10.1.1.35.3248 . doi :10.1145/351827.384257. S2CID 16705375. 代替 PDF ソース。
^ Edelkamp, Stefan; Wegener, Ingo (2000)、「 WEAK-HEAPSORTの性能について」、Stacs 2000 (PDF)、Lecture Notes in Computer Science、vol. 1770、Springer-Verlag、pp. 254– 266、CiteSeerX 10.1.1.21.1863、doi :10.1007/3-540-46541-3_21、ISBN 978-3-540-67141-1。
^ Bruun, Asger; Edelkamp, Stefan; Katajainen, Jyrki; Rasmussen, Jens (2010). 「弱ヒープとその類似物のポリシーベースベンチマーク」(PDF) .第9回国際実験アルゴリズムシンポジウム (SEA 2010) の議事録. コンピュータサイエンス講義ノート. 第6049巻. Springer-Verlag. pp. 424– 435. doi :10.1007/978-3-642-13193-6_36. ISBN
978-3-642-13192-9. 2017年8月11日時点のオリジナル（PDF）からアーカイブ。。
- Bruun, Asger; Edelkamp, Stefan; Katajainen, Jyrki; Rasmussen, Jens (2010). 「弱ヒープとその類似物のポリシーベースベンチマーク」. 実験アルゴリズム(PDF) . コンピュータサイエンス講義ノート. 第6049巻. pp. 424– 435. doi :10.1007/978-3-642-13193-6_36. ISBN 978-3-642-13192-9. S2CID 1334592. オリジナル（PDF）から2016年12月27日にアーカイブ – Semantic Scholar経由。
^ エデルカンプ、ステファン; エルマスリー、アムル; カタヤイネン、ユルキ (2012)、「理論と実践における弱ヒープ優先キュー群」(PDF)、第18回コンピューティング：オーストラレーシア理論シンポジウム (CATS 2012) の議事録、第128巻、ダーリングハースト、オーストラリア：オーストラリアコンピュータ協会、pp. 103– 112、ISBN 978-1-921770-09-8。

さらに読む

Edelkamp, Stefan; Elmasry, Amr; Katajainen, Jyrki (2013年11月). 「Weak heaps engineered」(PDF) . Journal of Discrete Algorithms . 23 : 83– 97. doi : 10.1016/j.jda.2013.07.002 .標準アルゴリズムを様々な方法で最適化するアルゴリズムのカタログを提供します。最適化の基準として、最悪ケースの実行時間、命令数、分岐予測ミス、キャッシュミス、要素比較、要素移動を考慮します。
Edelkamp, Stefan; Elmasry, Amr; Katajainen, Jyrki; Weiß, Armin (2013年7月). 弱ヒープとその仲間：最近の開発状況. 組合せアルゴリズム - 第24回国際ワークショップ.ルーアン, フランス. doi :10.1007/978-3-642-45278-9_1.

[1] Edelkamp, Stefan (2011年5月26日)、Pieterse, Vreda; Black, Paul E. (編)、「weak-heap」、Dictionary of Algorithms and Data Structures 、 2015年12月1日閲覧。

[Edelkamp12-2] Edelkamp, Stefan; Elmasry, Amr; Katajainen, Jyrki (2012年10月)、「弱ヒープデータ構造：その変種と応用」（PDF）、Journal of Discrete Algorithms、16 : 187– 205、CiteSeerX 10.1.1.455.1213、doi :10.1016/j.jda.2012.04.010、MR 2960353 。

[Dutton93-3] ダットン、ロナルド・D. (1993)、「弱ヒープソート」、BIT、33 (3): 372– 381、doi :10.1007/bf01990520、S2CID 5387832 。

[4] Bojesen, Jesper; Katajainen, Jyrki; Spork, Maz (2000). 「パフォーマンスエンジニアリングのケーススタディ：ヒープ構築」（PostScript） . ACM Journal of Experimental Algorithmics . 5 (15). CiteSeerX 10.1.1.35.3248 . doi :10.1145/351827.384257. S2CID 16705375. 代替 PDF ソース。

[5] Edelkamp, Stefan; Wegener, Ingo (2000)、「 WEAK-HEAPSORTの性能について」、Stacs 2000 (PDF)、Lecture Notes in Computer Science、vol. 1770、Springer-Verlag、pp. 254– 266、CiteSeerX 10.1.1.21.1863、doi :10.1007/3-540-46541-3_21、ISBN 978-3-540-67141-1。

[6] Bruun, Asger; Edelkamp, Stefan; Katajainen, Jyrki; Rasmussen, Jens (2010). 「弱ヒープとその類似物のポリシーベースベンチマーク」(PDF) .第9回国際実験アルゴリズムシンポジウム (SEA 2010) の議事録. コンピュータサイエンス講義ノート. 第6049巻. Springer-Verlag. pp. 424– 435. doi :10.1007/978-3-642-13193-6_36. ISBN 978-3-642-13192-9. 2017年8月11日時点のオリジナル（PDF）からアーカイブ。。
Bruun, Asger; Edelkamp, Stefan; Katajainen, Jyrki; Rasmussen, Jens (2010). 「弱ヒープとその類似物のポリシーベースベンチマーク」. 実験アルゴリズム(PDF) . コンピュータサイエンス講義ノート. 第6049巻. pp. 424– 435. doi :10.1007/978-3-642-13193-6_36. ISBN 978-3-642-13192-9. S2CID 1334592. オリジナル（PDF）から2016年12月27日にアーカイブ – Semantic Scholar経由。

[7] Bruun, Asger; Edelkamp, Stefan; Katajainen, Jyrki; Rasmussen, Jens (2010). 「弱ヒープとその類似物のポリシーベースベンチマーク」. 実験アルゴリズム(PDF) . コンピュータサイエンス講義ノート. 第6049巻. pp. 424– 435. doi :10.1007/978-3-642-13193-6_36. ISBN 978-3-642-13192-9. S2CID 1334592. オリジナル（PDF）から2016年12月27日にアーカイブ – Semantic Scholar経由。

[7] エデルカンプ、ステファン; エルマスリー、アムル; カタヤイネン、ユルキ (2012)、「理論と実践における弱ヒープ優先キュー群」(PDF)、第18回コンピューティング：オーストラレーシア理論シンポジウム (CATS 2012) の議事録、第128巻、ダーリングハースト、オーストラリア：オーストラリアコンピュータ協会、pp. 103– 112、ISBN 978-1-921770-09-8。