ペアリングヒープ
ペアリングヒープは、実装が比較的簡単で、実用的な償却パフォーマンスが優れているヒープデータ構造の一種として定義されています。
ペアリングヒープは、ヒープ順に並べられたマルチウェイツリー構造であり、簡略化されたフィボナッチヒープとして表すことができます。
これらは、プリムのMSTアルゴリズムなどのアルゴリズムを実装するための「堅牢な選択」と見なされ、次の操作をサポートします（最小ヒープを想定）-
- find-min −この関数は、ヒープの最上位要素を返す役割を果たします。
- 溶ける -この関数は、2つのルート要素を比較する役割を果たします。結果のルートが小さいほど、大きい要素とそのサブツリーがこのルートの子として追加されます。
- 挿入 −この関数は、挿入された要素の新しいヒープを作成し、元のヒープに融合する役割を果たします。
- 減少キー（オプション） −この関数は、減少させるキーをルートとするサブツリーを削除し、キーをより小さなキーに置き換えてから、結果をヒープにマージする役割を果たします。
- delete-min −この関数は、ルートを削除し、1つのツリーが残るまでそのサブツリーのメルドを繰り返し実行します。さまざまなマージ戦略が採用されています。
- 各ノードには左の子へのポインタがあり、左の子は子の次の兄弟を指します。
- ペアリングヒープの例を以下に示します-
ペアリングヒープの時間計算量の分析は、主にスプレー木の分析に触発されました。 delete-minあたりの償却時間はO（log n）と見なされ、find-min、meld、およびinsertの操作はO（1）の償却時間で実行されます。
-
対称最小-最大ヒープ
対称最小-最大ヒープ（SMMH）は、ルートを除く各ノードが正確に1つの要素を持つ完全なバイナリツリーとして定義されます。 SMMHのルートは空であり、SMMH内のノードの総数はm + 1です。ここで、mは要素の数です。 yをSMMHの任意のノードとします。 elements（y）を、yをルートとするサブツリー内の要素としますが、y内の要素（存在する場合）は除外します。 elements（y）j=∅と仮定します。 yは次の特性を満たします： yの左の子には、elements（y）の最小要素があります。 yの右の子（存在する場合）は、elements（y）に最大の要素を持ちます。 図1
-
ペアリングヒープのバリエーション
ペアリングヒープは、空のヒープ、またはルート要素とペアリングツリーの空のリストを含むペアリングツリーのいずれかです。 ヒープ順序プロパティでは、ノードの親がノード自体より大きくないことが必要です。 次の説明では、キーの減少操作をサポートしない純粋関数型ヒープについて検討します。 タイプPairingTree[Element]=Heap（element：Element、subheaps：List [PairingTree [Element]]） タイプPairingHeap[Element]=Empty | PairingTree [Element] ペアリングヒープには、最小ペアリ