最小-最大ヒープ（Min-Max Heap）とは？定義と主な特徴をわかりやすく解説

最小-最大ヒープとは

最小-最大ヒープ（Min-Max Heap）とは、最小レベル（偶数レベル）と最大レベル（奇数レベル）が交互に配置された完全二分木として定義されるデータ構造です。偶数レベルは0、2、4のように番号が振られ、奇数レベルは1、3、5のように番号が振られます。

以下の説明では、ルート要素は第0レベル（最初のレベル）に位置するものとします。

図：最小-最大ヒープの例

最小-最大ヒープの主な特徴

• キーによる順序付け： 最小-最大ヒープ内の各ノードには、通常「キー（key）」と呼ばれるデータメンバーが関連付けられており、このキーの値に基づいてヒープ内でのノードの順序が決定されます。
• ルートは最小要素： ルート要素は、最小-最大ヒープ全体における最小要素です。
• 最大要素の位置： 第1レベル（最大レベル＝奇数レベル）にある2つの要素のうちいずれか一方が、ヒープ全体の最大要素となります。
• 部分木における大小関係： yを最小-最大ヒープ内の任意のノードとしたとき、次の性質が成り立ちます。
  • yが最小レベル（偶数レベル）上にある場合、y.keyはyを根とする部分木内のすべてのキーの中で最小のキーです。
  • yが最大レベル（奇数レベル）上にある場合、y.keyはyを根とする部分木内のすべてのキーの中で最大のキーです。
• ノードの呼称： 最小レベル上にあるノードは「最小ノード」、最大レベル上にあるノードは「最大ノード」と呼ばれます。

最大-最小ヒープとの違い

最大-最小ヒープ（Max-Min Heap）は、最小-最大ヒープとは逆の性質を持つデータ構造です。最大-最小ヒープでは、最大値がルートに格納され、最小値はルートの子のいずれかに格納されます。

このような双方向のヒープ構造は、最小値と最大値の両方を効率的に取り出せるため、両端優先度付きキュー（Double-ended Priority Queue）の実装などに活用されています。