優先順位付きキュー 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)となります。