ヒープ Heap

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の処理を終了します。




ヒープを使って以下のデータ構造とアルゴリズムを実装することができます。

• 優先順位付きキュー　Priority Queue
• ヒープソート Heap Sort

優先順位付きキュー Priority Queue

データ構造には主にデータを「追加する」と「取り出す」という操作あります。そしてデータ構造にはデータを取り出すときのルールがあります。スタックはデータの中で最後に追加されたもの（一番短い時間滞在したもの）、キューはデータの中で最初に追加されたもの（一番長い時間滞在したもの）、を優先的に取り出します。つまりデータを取り出す優先度が制約によって決められています。一方、データがもつあるキーを基準にして優先度が高いものからデータを取り出す優先順位付きキューも、システムの制御やアルゴリズムの実装において重要な役割を果たします。

例として、プリンタのジョブ管理を考えてみます。１つのプリンタを共有している複数のＰＣがあると仮定します。もし、プリンタがFIFOのルールに従ったキューでジョブを管理すれば、１０００ページのジョブがキューに到着し、その後１ページのジョブがキューに到着した場合、このプリンタは先に到着した１０００ページのジョブを印刷し、それが終了した後、１ページのジョブを印刷するでしょう。このようなケースでは、先に１ページのジョブを印刷して、その後１０００ページのジョブを印刷した方が良いと考えられます。なぜなら、ジョブが実行されるまでの全体としての"待ち時間"が短くなるからです。この場合は、ページ数が少ないジョブの優先度を高くするべきです。

ここでは、整数のデータを格納する優先順位付きキューについて考えます。整数が追加されていき、キューの中で値が大きいものから優先的に取り出されます。

Priority Queue の操作

• insert( x ): キューにデータ x を挿入する
• get(): キューから最も優先度の高いデータを取り出す

データ構造はリアルタイムで（動的に）値の追加や取り出しが行われるので、いかにこれらの操作を効率良く行うかが重要になります。例えば、スタックやキューのデータ構造における操作は、追加も取り出しもO(1)の計算量で行うことができます。しかし、優先順位付きキューはそうはいきません。ここで考えられるのがデータの探索と整列（次章で学習します）ですが、データを取り出す度に優先度の高いものを探索していたのではO(n)の計算量が必要ですし、データを追加する（または取り出す）度にデータを優先度順に並び変えていては探索するよりも効率が悪くなります。優先順位付きキューの操作を効率良く行うために、ヒープの概念を用います。

ヒープ（Heap）

整数型のデータが格納される優先順位付きキューをヒープを用いて実装します。値が大きいものほど優先度が高いものとします。実装に必要なものは配列によるスタックとキューと同じく、データを格納するための整数型1次元配列bufferです。このbufferをヒープとみなして優先順位付きキューに対する操作を行います。優先順位付きキューにはinsert(x)とgetの操作がありました。

insert(x)

ヒープのデータ構造において、新しいデータをinsertすることができる場所はヒープのサイズを1つ増やしたヒープの末尾です。下図に示すように、ヒープの末尾にデータを追加すると（1.）、それがヒープの制約を破る可能性があります（2.）。従って、そのデータが追加されたヒープの末尾を起点にupHeapを施します（2.→3.）。

get

ヒープのルートには必ずデータの中で一番優先度が高い要素が含まれます。従って下図に示すように、getでルートの要素を取り出します（1.）。ルートが実質空になるので、ヒープの末尾の要素をルートに移動しヒープのサイズを1つ減らします（2.）。ルートの要素がヒープの制約を破る可能性があるので（2.）、ルートを起点としてdownHeapを施します（2.→3.）。




以下のプログラムはヒープによって優先順位付きキューを実現し、キューへのデータの追加・取り出しをシミュレーションします。プログラムは”insert x”（xは整数）と入力されるとキューにxを追加し、”get”と入力されるとキューの中で一番値が大きいものを取り出し出力します。

001 #include<iostream>
002 #include<string>
003 #include<algorithm>
004 using namespace std;
005 #define MAX 10000
006 
007 class PriorityQueue{
008     public:
009     int size;
010     int buffer[MAX + 1];
011     
012     PriorityQueue(){size = 0;}
013     
014     void insert(int x){
015         size++;
016         buffer[size] = x;
017         upHeap(size);
018     }
019     
020     int get(){
021         int v = buffer[1];
022         buffer[1] = buffer[size];
023         size--;
024         downHeap(1);
025         return v;
026     }
027     
028     private:
029     
030     void upHeap( int cursor ){
031         int parent;
032         while(1){
033             parent = cursor / 2;
034             if ( parent < 1 ) break;
035             if ( buffer[parent] < buffer[cursor] ){
036                 swap(buffer[parent], buffer[cursor]);
037             } else break;
038             cursor = parent;
039         }
040     }
041     
042     void downHeap( int cursor ){
043         int child;
044         while(1){
045             if ( cursor > size/2 ) break;
046             child = cursor * 2; // left child
047             if ( child < size && buffer[child] < buffer[child+1] ) child++;
048             if ( buffer[cursor] < buffer[child] ){
049                 swap( buffer[cursor], buffer[child] );
050             } else break;
051             cursor = child;
052         }
053     }
054 };
055 
056 int main(void){
057     PriorityQueue PQ = PriorityQueue();
058     int x;
059     string command;
060     
061     while(1){
062         cin >> command;
063         if ( command == "insert" ){
064             cin >> x;
065             PQ.insert(x);
066         } else if ( command == "get" ){
067             cout << PQ.get() << endl;
068         } else break;
069     }
070     
071     return 0;
072 }

main関数

優先順位付きキューのオブジェクトPQを操作します。

insert (x)

ヒープのサイズsizeを1つ増やし、ヒープの末尾をしめすbuffer[size]にxを追加します。ヒープの条件を保つためにヒープの末尾を示すsizeを起点にupHeapを施します。

get

ヒープのルートの要素であるbuffer[1]を一時変数vに記録し、ヒープの末尾の要素buffer[size]をルートへ移動します。末尾の要素を空にするので、ヒープのサイズsizeを1つ減らします。ヒープの条件を保つためルートである1を起点にdownHeapを施します。

upHeap

下図を参照して下さい。引数cursorを起点にupHeapを行います。親の要素buffer[parent]が起点の要素buffer[cursor]よりも小さい場合、それらを交換します。この処理をcursorを1つ上に移動してヒープの条件を満たすまで繰り返します。

downHeap

下図を参照して下さい。引数cursorを起点にdownHeapを行います。子の要素buffer[child]が起点の要素buffer[cursor]よりも大きい場合、それらを交換します。047行目で左と右の子のうち要素の値が大きいものを選んでいます。この処理を、cursorを選ばれた子の方向に1つ下に移動してヒープの条件を満たすまで繰り返します。



ヒープは完全２分木であり、要素の数をnとすれば木の高さはlognとなります。upHeapとdownHeapの計算量はいづれもO(logn)です。従って、優先順位付きキューに対するinsertとgetの計算量は、いづれもO(logn)となります。