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

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

この章の概要

この章の概要です。


優先度付きキュー

優先度付きキュー(プライオリティキュー)は、要素1つ1つに優先度が割り当てられており、その優先度に従った順に取り出されるというデータ構造です。キュー第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(size_t size)
{
    struct PriorityQueue_tag* 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)
{
    bool ret = ppps_int_heap_insert( queue->heap, value );
    assert( ret );
}

/*
    優先度付きキューから要素を取り出す
*/
int priority_queue_dequeue(PriorityQueue queue)
{
    int value;
    bool ret = ppps_int_heap_remove_root( queue->heap, &value );
    assert( ret );

    return value;
}

/*
    優先度付きキューが空かどうか調べる
*/
bool 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

#include <stdbool.h>


/*
    優先度付きキュー型
*/
typedef struct PriorityQueue_tag* PriorityQueue;


/*
    優先度付きキューを作る

    引数:
        size:   格納できる要素数
    戻り値:
        作成された優先度付きキュー。
        使い終わったら、priority_queue_delete関数に渡して削除する。
*/
PriorityQueue priority_queue_create(size_t 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:  優先度付きキュー
    戻り値:
        優先度付きキューが空であれば true を返し、空でなければ false を返す。
*/
bool 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(l og n) O(l og 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 に保存 Facebook でシェア
X で ポストフォロー LINE で送る noteで書く
rss1.0 取得ボタン RSS 管理者情報 プライバシーポリシー
先頭へ戻る