この章の概要です。
優先度付きキュー（プライオリティキュー、順位キュー）は、キュー（第６章）の一種ですが、取り出すルールに特徴があります。
通常のキューでは、要素は格納した順番通りに取り出されます。
優先度付きキューの場合は、要素に何らかの方法で優先度が付けられており、その優先度に従った順に取り出されます。
例えば、整数を格納する優先度付きキューであれば、その要素の値自体を優先度と考え、
優先度の昇順に取り出されるといった具合です。
この方法の場合、適当に複数の要素を格納した後で、取り出し操作を繰り返し行えば、昇順に並んだ要素の組が得られます。
なお、優先度のルールは自由に決めて構いません。
優先度付きキューを実装する手段は色々とあります。 単なる配列だけで実現することもできますし、リスト構造や、木構造を使うこともできます。 また、同じデータ構造を利用しても、考え方によって性能に変化が現れます。
優先度に従って要素を取り出すためには、２つの考え方があります。
１つは、要素を格納するときには、特に気にせず格納処理を行い、
要素を取り出すときに、優先度の高いものを探すという考え方です。
もう１つはその反対で、要素を格納するときに、優先度の順に並ぶように挿入を行い、
要素を取り出すときには、単に先頭にある要素を取り除くという考え方です。
これらの考え方に基づいて、配列を使って実装したとすると、
前者の方法では、格納は O(1) の計算量になるので速いですが、取り出すときには O(n) になり遅くなります。
後者の方法では、格納は O(n) となり遅くなりますが、取り出すときは O(1) で済みます。
このように、優先度付きキューは実装の仕方によって、性能面に特徴的な差が生まれます。 ただ、実際的には、配列やリスト構造を使うよりも、木構造、とりわけヒープ（第９章）を利用する方法が、高い性能を示すため、 多く利用されています。 本章でも、ヒープを使った実装を取り上げます。
実のところ、ヒープを使った実装は、ヒープさえ用意できていれば終了したも同然です。
優先度付きキューに要素を格納する操作は、ヒープに要素を追加する操作を行うだけですし、
優先度付きキューから要素を取り出す操作は、ヒープの根を取り出す操作を行うだけで実現できます。
ヒープ自体の実装は、第９章で解説しているので、そちらを確認して下さい。 ここでは、コードライブラリにあるヒープの実装を使って、 優先度付きキューを作ってみます。
/* priority_queue.c */ #include "priority_queue.h" #include <stdio.h> #include <stdlib.h> #include <assert.h> #include "ppps_int_heap.h" static void* xmalloc(size_t size); struct PriorityQueue_tag { PPPSIntHeap heap; }; /* 優先度付きキューを作る */ PriorityQueue priority_queue_create(int size) { struct PriorityQueue_tag* queue; assert( size > 0 ); queue = xmalloc( sizeof(struct PriorityQueue_tag) ); queue->heap = ppps_int_heap_create( size ); return queue; } /* 優先度付きキューを削除する */ void priority_queue_delete(PriorityQueue queue) { ppps_int_heap_delete( queue->heap ); free( queue ); } /* 優先度付きキューに要素を入れる */ void priority_queue_enqueue(PriorityQueue queue, int value) { int ret; ret = ppps_int_heap_insert( queue->heap, value ); assert( ret != 0 ); } /* 優先度付きキューから要素を取り出す */ int priority_queue_dequeue(PriorityQueue queue) { int value; int ret; ret = ppps_int_heap_remove_root( queue->heap, &value ); assert( ret != 0 ); return value; } /* 優先度付きキューが空かどうか調べる */ int priority_queue_is_empty(PriorityQueue queue) { return ppps_int_heap_getsize( queue->heap ) == 0; } /* エラーチェック付きの malloc関数 */ void* xmalloc(size_t size) { void* p = malloc( size ); if( p == NULL ){ fputs( "メモリ割り当てに失敗しました。", stderr ); exit( EXIT_FAILURE ); } return p; }
/* priority_queue.h */ #ifndef PRIORITY_QUEUE_H #define PRIORITY_QUEUE_H /* 優先度付きキュー型 */ typedef struct PriorityQueue_tag* PriorityQueue; /* 優先度付きキューを作る 引数： size: 格納できる要素数 戻り値： 作成された優先度付きキュー。 使い終わったら、priority_queue_delete関数に渡して削除する。 */ PriorityQueue priority_queue_create(int size); /* 優先度付きキューを削除する 引数： queue: 優先度付きキュー */ void priority_queue_delete(PriorityQueue queue); /* 優先度付きキューに要素を入れる 引数： queue: 優先度付きキュー value: 入れる要素 */ void priority_queue_enqueue(PriorityQueue queue, int value); /* 優先度付きキューから要素を取り出す 引数： queue: 優先度付きキュー 戻り値： 取り出された要素 */ int priority_queue_dequeue(PriorityQueue queue); /* 優先度付きキューが空かどうか調べる 引数： queue: 優先度付きキュー 戻り値： 優先度付きキューが空であれば 0以外を返し、空でなければ 0 を返す。 */ int priority_queue_is_empty(PriorityQueue queue); #endif
/* main.c */ #include <stdio.h> #include "priority_queue.h" int main(void) { PriorityQueue queue = priority_queue_create( 16 ); priority_queue_enqueue( queue, 5 ); priority_queue_enqueue( queue, 3 ); priority_queue_enqueue( queue, 7 ); priority_queue_enqueue( queue, 2 ); priority_queue_enqueue( queue, 9 ); while( !priority_queue_is_empty(queue) ){ printf( "%d\n", priority_queue_dequeue(queue) ); } priority_queue_delete( queue ); return 0; }
実行結果：
2 3 5 7 9
priority_queue.c の各関数の実装を見ると、ほとんど、ヒープ側に用意した関数を呼び出すだけなのが分かると思います。 そのため、性能面は事実上、ヒープの性能によって決まると言えます。 ヒープは、要素の挿入、根の削除に要する計算量はいずれも O(log n) で行えるので、ヒープによる優先度付きキューの性能もこれと同じになります。
また、優先度付きキューを使って、複数の要素を追加し、優先度順にすべて取り出すことで、 ソートが実現できることは明らかです。 ヒープによって実装されて優先度付きキューを使用した場合、 この一連の操作は、ヒープソート（【整列】第８章）そのものです。
優先度付きキューを実装する方法は数多くありますが、 ヒープによる実装が、要素の追加、削除、参照の性能が良いので、よく使われています。
更なる改良として、ペアリングヒープや、フィボナッチヒープという構造を使うことがあります。
参考として、各データ構造を使ったときの性能（計算量）をまとめると、次のようになります。
| 使用するデータ構造 | 追加 | 削除 | 参照 |
|---|---|---|---|
| 配列（ソート済みに保たない） | O(1) | O(n) | O(n) |
| 配列（ソート済みに保つ） | O(n) | O(1) | O(1) |
| 線形リスト（ソート済みに保たない） | O(1) | O(n) | O(n) |
| 線形リスト（ソート済みに保つ） | O(n) | O(1) | O(1) |
| 二分探索木 | O(log n) | O(log n) | O(log n) |
| ヒープ | O(log n) | O(log n) | O(1) |
削除と参照は、優先度の高い要素に対するものです。
ソート済みに保たない考え方の配列と線形リストの場合、追加は何も気にすることが無いので O(1) で済みますが、
削除と参照は、最大で要素数分の走査が必要になるので O(n) になります。
一方、ソート済みに保つ場合は、適切な位置への追加が必要なので O(n) になってしまいますが、
削除と参照は、先頭要素を対象にするだけで済むので O(1) で済みます。
二分探索木は、各種操作がバランスよく速いですが、第８章で見たように、バッドケースではこれより遅くなり得ます。
ヒープ（二分ヒープ）では、追加と削除は適切な位置を探す必要性から、O(log n) になりますが、
参照は根を見るだけですから O(1) で済みます。
この表を見て比較してみると、確かに、ヒープによる実装が最もバランスよく性能が高いことが分かります。
問題① 配列による優先度付きキューを「要素を格納するときには、特に気にせず格納処理を行い、 要素を取り出すときに、優先度の高いものを探すという考え方」で実装して下さい。
問題② 配列による優先度付きキューを「要素を格納するときに、優先度の順に並ぶように挿入を行い、 要素を取り出すときには、単に先頭にある要素を取り除くという考え方」で実装して下さい。
'2014/12/14 新規作成。