対称最小-最大ヒープ

対称最小-最大ヒープ（SMMH）は、ルートを除く各ノードが正確に1つの要素を持つ完全なバイナリツリーとして定義されます。 SMMHのルートは空であり、SMMH内のノードの総数はm + 1です。ここで、mは要素の数です。

yをSMMHの任意のノードとします。 elements（y）を、yをルートとするサブツリー内の要素としますが、y内の要素（存在する場合）は除外します。 elements（y）j=∅と仮定します。 yは次の特性を満たします：

• yの左の子には、elements（y）の最小要素があります。
• yの右の子（存在する場合）は、elements（y）に最大の要素を持ちます。

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

yが81のノードを表す場合、elements（y）={7、15、31、41}; yの左の子は、elements（y）の最小要素6を持ちます。 yの右の子は、elements（y）の最大要素41を持ちます。このSMMHのすべてのノードyが指定されたプロパティを満たしていることを確認できます。

SMMHは完全な二分木として示されるため、完全な二分木の配列への標準マッピングを実装する暗黙のデータ構造として格納されます。 m =1の場合、最小要素と最大要素は同じであり、SMMHのルートの左の子に含まれます。

m> 1の場合、最小要素はルートの左側の子にあり、最大要素はルートの右側の子にあります。したがって、getMinおよびgetMax操作はO（1）時間を消費します。

次の条件が当てはまる場合、ルートが空で、他のすべてのノードに1つの要素があるm+1ノードの完全な二分木がSMMHであることが簡単にわかります-

A1-右の兄弟を持つすべてのノードyについて、yの要素はyの右の兄弟の要素以下です。

A2 −祖父母を持つすべてのノードyについて、祖父母の左の子の要素はyの要素以下です。

A3-祖父母を持つすべてのノードyについて、祖父母の右の子の要素はyの要素以上です。

プロパティA1がノードyで満たされている場合、A2とA3の最大1つがyで違反される可能性があることに注意してください。プロパティA1からA3を実装すると、要素を挿入および削除するための単純なアルゴリズムに到達します。これらのアルゴリズムは、最小ヒープと最大ヒープに対応するアルゴリズムを単純に適応させたものです。それらの複雑さはO（log m）です。

ここでは、挿入操作を指定します。図1のSMMHに3を挿入するとします。SMMHは完全な二分木であるため、図2に示す位置でSMMHに新しいノードを追加する必要があります。新しいノードにはBというラベルが付けられます。

この例では、Bは空のノードを示します。これで、ノードBに3が挿入されました。