ペアリングヒープのバリエーションとは？最小ヒープと最大ヒープの違いを解説

ペアリングヒープの定義

ペアリングヒープ（pairing heap）は、「空のヒープ」であるか、あるいは「ルート要素」と「空でもよいペアリングツリー（ペアリング木）のリスト」から構成されるペアリングツリーのいずれかとして定義されます。

ヒープ順序性（heap ordering property）では、任意のノードの親は、そのノード自身より大きくなってはならないと規定されます。

以下の説明では、decrease-key（キー値減算）操作をサポートしない、純粋関数型のヒープを想定します。

型定義

type PairingTree[Element] = Heap(element: Element, subheaps: List[PairingTree[Element]])
type PairingHeap[Element] = Empty | PairingTree[Element]

2種類のペアリングヒープ：最小ヒープと最大ヒープ

ペアリングヒープには、「最小ペアリングヒープ（min pairing heap）」と「最大ペアリングヒープ（max pairing heap）」という2つの種類があります。

• 最小ペアリングヒープ： 最小優先度キュー（min priority queue）を実現したい場合に用いられます。
• 最大ペアリングヒープ： 最大優先度キュー（max priority queue）の実装に使用されます。

本記事では、最大ペアリングヒープについて明示的に取り上げて説明します。最小ペアリングヒープも、まったく同じ考え方の対称的な適用によって実現できます。

最大ペアリングヒープの構造

最大ペアリングヒープは、単純に「最大木（max tree）」として定義されます。つまり、どのノードの値も、その子孫となるすべてのノードの値以上になるような木構造です。

下図に、4つの最大ペアリングヒープの例を示します。ここで注目すべき重要なポイントは、ペアリングヒープは二分木である必要がないという点です。各ノードは任意の個数の子を持つことができ、この柔軟な構造こそが、マージ（併合）操作を高速に行える理由となっています。

補足：ペアリングヒープの特徴

ペアリングヒープは、実装が非常にシンプルでありながら、マージや挿入が効率的に行えることから、実務でも広く利用されているデータ構造です。一方で、その償却計算量の厳密な解析は難しく、delete-min（最小要素の削除）などの操作に対して O(log n) の償却計算量が成り立つかどうかは、計算機科学における有名な未解決問題の一つとされています。