アルゴリズムとデータ構造編【データ構造】 第10章 優先度付きキュー

先頭へ戻る

この章の概要

この章の概要です。


優先度付きキュー

優先度付きキュー(プライオリティキュー、順位キュー)は、キュー(第6章)の一種ですが、取り出すルールに特徴があります。

通常のキューでは、要素は格納した順番通りに取り出されます。優先度付きキューの場合は、要素に何らかの方法で優先度が付けられており、その優先度に従った順に取り出されます。

例えば、整数を格納する優先度付きキューであれば、その要素の値自体を優先度と考え、優先度の昇順に取り出されるといった具合です。この方法の場合、適当に複数の要素を格納した後で、取り出し操作を繰り返し行えば、昇順に並んだ要素の組が得られます。なお、優先度のルールは自由に決めて構いません。

優先度付きキューを実装する手段はいろいろとあります。単なる配列だけでも実現できますし、リスト構造や、木構造を使うこともできます。また、同じデータ構造を利用しても、考え方によって性能に変化が現れます。

優先度に従って要素を取り出すためには、2つの考え方があります。

1つは、要素を格納するときには、特に気にせず格納処理を行い、要素を取り出すときに、優先度の高いものを探すという考え方です。

もう1つはその反対で、要素を格納するときに、優先度の順に並ぶように挿入を行い、要素を取り出すときには、単に先頭にある要素を取り除くという考え方です。

これらの考え方に基づいて、配列を使って実装したとすると、前者の方法では、格納は O(1) の計算量になるので速いですが、取り出すときには O(n) になり遅くなります。後者の方法では、格納は O(n) となり遅くなりますが、取り出すときは O(1) で済みます。

このように、優先度付きキューは実装の仕方によって、性能面に特徴的な差が生まれます。ただ、実際的には、配列やリスト構造を使うよりも、木構造、とりわけヒープ(第9章)を利用する方法が、高い性能を示すため、多く利用されています。本章でも、ヒープを使った実装を取り上げます。


ヒープによる実装

実のところ、ヒープを使った実装は、ヒープさえ用意できていれば終了したも同然です。優先度付きキューに要素を格納する操作は、ヒープに要素を追加する操作を行うだけですし、優先度付きキューから要素を取り出す操作は、ヒープの根を取り出す操作を行うだけで実現できます。

ヒープ自体の実装は、第9章で解説しているので、そちらを確認してください。ここでは、コードライブラリにあるヒープの実装を使って、優先度付きキューを作ってみます。

/* 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_INCLUDED
#define PRIORITY_QUEUE_H_INCLUDED


/*
    優先度付きキュー型
*/
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) で行えるので、ヒープによる優先度付きキューの性能もこれと同じになります。

また、優先度付きキューを使って、複数の要素を追加し、優先度順にすべて取り出すことで、ソートが実現できることは明らかです。ヒープによって実装されて優先度付きキューを使用した場合、この一連の操作は、ヒープソート【整列】第8章)そのものです。

まとめ

優先度付きキューを実装する方法は数多くありますが、ヒープによる実装が、要素の追加、削除、参照の性能が良いので、よく使われています。

さらなる改良として、ペアリングヒープや、フィボナッチヒープという構造を使うことがあります。

参考として、各データ構造を使ったときの性能(計算量)をまとめると、次のようになります。

使用するデータ構造 追加 削除 参照
配列(ソート済みに保たない) 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) で済みます。

二分探索木は、各種操作がバランスよく速いですが、第8章で見たように、バッドケースではこれより遅くなり得ます。

ヒープ(二分ヒープ)では、追加と削除は適切な位置を探す必要性から、O(log n) になりますが、参照は根を見るだけですから O(1) で済みます。


練習問題

問題① 配列による優先度付きキューを「要素を格納するときには、特に気にせず格納処理を行い、要素を取り出すときに、優先度の高いものを探すという考え方」で実装してください。

問題② 配列による優先度付きキューを「要素を格納するときに、優先度の順に並ぶように挿入を行い、要素を取り出すときには、単に先頭にある要素を取り除くという考え方」で実装してください。


解答ページはこちら


参考リンク



更新履歴

'2014/12/14 新規作成。



前の章へ (第9章 ヒープ)

次の章へ (第11章 両端キュー)

アルゴリズムとデータ構造編のトップページへ

Programming Place Plus のトップページへ


はてなブックマーク Pocket に保存 Twitter でツイート Twitter をフォロー
Facebook でシェア Google+ で共有 LINE で送る rss1.0 取得ボタン RSS
管理者情報 プライバシーポリシー