対称最小-最大ヒープ（SMMH）とは？定義・基本性質・挿入操作を解説

対称最小-最大ヒープ（SMMH）とは

対称最小-最大ヒープ（Symmetric Min-Max Heap、略してSMMH）は、根以外のすべてのノードがちょうど1つの要素を持つ完全二分木として定義されるデータ構造です。根は常に空であり、SMMHのノード総数は m + 1 となります（m は格納されている要素の数）。

SMMHが満たすべき基本性質

SMMHの任意のノードを y とします。elements(y) を「y を根とする部分木に含まれる要素のうち、y 自身の要素（存在する場合）を除いたもの」と定義します。elements(y) が空でないとき、y は以下の2つの性質を満たします。

• y の左の子は、elements(y) の中の最小要素を持つ。
• y の右の子（存在する場合）は、elements(y) の中の最大要素を持つ。

具体例：12個の要素を持つSMMH

図1に、12個の要素を持つSMMHの例を示します。

例えば、y を要素 81 を持つノードとすると、elements(y) = {7, 15, 31, 41} となります。このとき、y の左の子は elements(y) の最小要素 7 を持ち、y の右の子は最大要素 41 を持ちます。同様に確認することで、このSMMHのすべてのノード y が上記の性質を満たしていることがわかります。

配列による格納とO(1)の最小・最大取得

SMMHは完全二分木として表現されるため、完全二分木を配列に対応付ける標準的なマッピングを用いた暗黙的データ構造（implicit data structure）として格納できます。

m = 1 の場合、最小要素と最大要素は同一であり、根の左の子に格納されます。一方、m > 1 の場合、最小要素は必ず根の左の子に、最大要素は必ず根の右の子に存在します。したがって、getMin および getMax の各操作は O(1) 時間で実行できます。

SMMHを特徴付ける3つの条件

根が空で、それ以外の各ノードが1つの要素を持つ m + 1 ノードの完全二分木がSMMHであるための必要十分条件は、次の3つの条件がすべて成り立つことです。

• A1：右の兄弟を持つ任意のノード y について、y の要素はその右の兄弟の要素以下である。
• A2：祖父ノードを持つ任意のノード y について、祖父の左の子の要素は y の要素以下である。
• A3：祖父ノードを持つ任意のノード y について、祖父の右の子の要素は y の要素以上である。

ここで重要なのは、ノード y で条件 A1 が満たされているならば、y で違反しうるのは A2 と A3 のうち高々1つだけであるという点です。条件 A1〜A3 に基づくことで、要素の挿入・削除のためのシンプルなアルゴリズムを構築できます。これらのアルゴリズムは、最小ヒープおよび最大ヒープ向けの対応するアルゴリズムを単純に応用したものであり、計算量はいずれも O(log m) です。

挿入操作の流れ

最後に、挿入操作の具体的な手順を見てみましょう。図1のSMMHに要素 3 を挿入する場合を考えます。SMMHは完全二分木であるため、まず図2に示す位置に新しいノードを追加する必要があります。この新しいノードを B と呼びます。

この例では、B は一時的に空のノードとなります。その後、要素 3 をノード B に挿入し、条件 A1〜A3 が再び満たされるように必要に応じて要素の入れ替えを行うことで、挿入が完了します。