ALGORITHM NOTE ヒープ　Heap

ヒープ　Heap

2007.04.10 14:09 データ構造

Priority Queue を効率よく実装するためのデータ構造が ヒープ(heap) です。ヒープもまたデータ構造であり、その論理的構造は完全２分木となっています。完全２分木を１次元配列によって表現するために、木のノードの番号と配列のインデックスを下図のように対応付けます。便宜上インデックスは1から始めます。

木のルートを配列のインデックス1と対応させ（0でないことに注意して下さい）、その左の子を2、右の子を3と対応させます。同様に、各ノードの番号をkとすると、その親、左の子、右の子のインデックスは以下のようになります。

インデックス	k
親のインデックス	parent = k / 2
左の子のインデックス	left = 2 × k
右の子のインデックス	right = 2 × k+ 1

例えば、ノード 5 の
親のノードは parent = k / 2 = 5 / 2 = 2
左の子のノードは left = 2 × k = 2 × 5 = 10
右の子のノードは right = 2 × k + 1 = 2 × 5 + 1 = 11
となります。

ヒープの各ノード（配列の各要素）に、データが格納されます。ヒープにはデータの並びにおける制約があり下図に示すようにMaximum HeapとMinimum Heapの2つのタイプがあります。

上図は整数のデータを格納するヒープを表しています。

マキシマムヒープ Maximum Heap

マキシマムヒープでは上図（左）に示すように、各ノードのキーがその親ノードのキーよりも小さいか等しくなければなりません。ヒープのルートのキーが必ず最大となります。

ミニマムヒープ Minimum Heap

ミニマムヒープは上図（右）に示すように、各ノードのキーがその親ノードのキーよりも大きいか等しくなければなりません。ヒープのルートのキーが必ず最小となります。

マキシマムヒープもミニマムヒープも、データが完全に整列されている必要はありません。左の子と右の子のキーの大小関係に制約はなく、親ノードと子ノードのキーの大小関係にのみ制約があります。

ヒープには、ヒープのユーザ（プログラムやアルゴリズム）がそれに対してなんらかの操作（データの追加・取り出し・入れ替えなど）をした直後に、ヒープの条件（マキシマムヒープまたはミニマムヒープ）を維持するための処理が不可欠となります。この条件を維持するための処理は以下のものを含みます。

upHeap()
downHeap()

これらの処理を詳しく見てみましょう。ここでは、常にマキシマムヒープの条件を維持することを考えます。

upHeap

下図に示すように、upHeapは起点となるノードcursorの要素を、ヒープの条件を満たすまで木のルートへ向かって上へ移動します。まず1.においてcursorの要素である60が親の要素である8よりも大きくマキシマムヒープの条件を満たしていないので、2.でこれらの要素を交換しcursorを上に移動します。さらに3.においてcursorの要素である60が親の要素である25よりも大きくマキシマムヒープの条件を満たしていないので、4.でこれらの要素を交換し、cursorを上に移動します。5.でマキシマムヒープの条件が満たされたのでupHeapの処理を終了します。

downHeap

下図に示すように、downHeapは起点となるノードcursorの要素を、ヒープの条件を満たすまで木の葉（子を持たないノード）へ向かって下へ移動します。まず1.においてcursorの要素である6が子の要素である25よりも小さくマキシマムヒープの条件を満たしていないので、2.でこれらの要素を交換しcursorを下に移動します。ここで、cursorの子はノード2（左の子）とノード3（右の子）がありますが、こられのうちキーの値が大きいものを選んで比較します。この場合は25と21を比べ、25の方が大きいので、ノード2を選びます。3.においてcursorの要素である6が子の要素である12よりも小さいので、4.でこれらの要素を交換し、cursorを下に移動します。5.でマキシマムヒープの条件が満たされるのでdownHeapの処理を終了します。