先頭へ戻る

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

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

先頭へ戻る

問題①

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


本編のヒープによる実装と同じインタフェースを保つように作れば、priority_queue.c 以外の変更は不要です。

// priority_queue.c

#include "priority_queue.h"
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#define SWAP(type,a,b) { type work = a; a = b; b = work; }

static void* xmalloc(size_t size);

struct PriorityQueue_tag {
    int*   data;
    size_t count;
    size_t size;
};


/*
    優先度付きキューを作る
*/
PriorityQueue priority_queue_create(size_t size)
{
    struct PriorityQueue_tag* queue = xmalloc( sizeof(struct PriorityQueue_tag) );
    queue->data = malloc( sizeof(int) * size );
    queue->count = 0;
    queue->size = size;

    return queue;
}

/*
    優先度付きキューを削除する
*/
void priority_queue_delete(PriorityQueue queue)
{
    free( queue->data );
    free( queue );
}

/*
    優先度付きキューに要素を入れる
*/
void priority_queue_enqueue(PriorityQueue queue, int value)
{
    assert( queue->count + 1 < queue->size );

    queue->data[queue->count] = value;
    queue->count++;
}

/*
    優先度付きキューから要素を取り出す
*/
int priority_queue_dequeue(PriorityQueue queue)
{
    assert( !priority_queue_is_empty(queue) );

    size_t min_index = 0;
    int min = queue->data[min_index];

    for( size_t i = 1; i < queue->count; ++i ){
        if( min > queue->data[i] ){
            min = queue->data[i];
            min_index = i;
        }
    }

    // 取り出した要素の後続を詰めなおすと遅いので、
    // 末尾の要素と入れ替えることで、削除を実現する。
    // この後、queue->count がデクリメントされるので、
    // 交換先の要素は、新たな要素が追加されない限り、参照されることは無い。
    SWAP(int, queue->data[min_index], queue->data[queue->count - 1]);

    queue->count--;

    return min;
}

/*
    優先度付きキューが空かどうか調べる
*/
bool priority_queue_is_empty(PriorityQueue queue)
{
    return queue->count == 0;
}



/*
    エラーチェック付きの malloc関数
*/
void* xmalloc(size_t size)
{
    void* p = malloc( size );
    if( p == NULL ){
        fputs( "メモリ割り当てに失敗しました。", stderr );
        exit( EXIT_FAILURE );
    }
    return p;
}

要素数を常に管理しておけば、要素の追加の際に、すぐに位置が定まるので O(1) で実現できます。

要素を取り出す際には、キュー全体を調べて、一番優先度が高いものを探す必要があります。この過程があるため、O(n) になってしまいます。

また、配列なので、要素を削除すると空きが生まれてしまいます。ここで後続の要素を詰めなおす実装をすると、非常に遅くなりますが、このサンプルプログラムのように、アクセスされることがない要素と入れ替えることで実現すれば、効率が良くなります。

問題②

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


問題①同様に、priority_queue.c だけを修正します。

// priority_queue.c

#include "priority_queue.h"
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

static void* xmalloc(size_t size);

struct PriorityQueue_tag {
    int*   data;
    size_t count;
    size_t size;
};


/*
    優先度付きキューを作る
*/
PriorityQueue priority_queue_create(size_t size)
{
    struct PriorityQueue_tag* queue = xmalloc( sizeof(struct PriorityQueue_tag) );
    queue->data = malloc( sizeof(int) * size );
    queue->count = 0;
    queue->size = size;

    return queue;
}

/*
    優先度付きキューを削除する
*/
void priority_queue_delete(PriorityQueue queue)
{
    free( queue->data );
    free( queue );
}

/*
    優先度付きキューに要素を入れる
*/
void priority_queue_enqueue(PriorityQueue queue, int value)
{
    assert( queue->count + 1 < queue->size );

    if( queue->count == 0 ){
        queue->data[0] = value;
    }
    else{
        size_t i;
        for( i = queue->count; i >= 1 && queue->data[i - 1] < value; --i ){
            queue->data[i] = queue->data[i - 1];
        }
        queue->data[i] = value;
    }

    queue->count++;
}

/* 優先度付きキューから要素を取り出す */
int priority_queue_dequeue(PriorityQueue queue)
{
    assert( !priority_queue_is_empty(queue) );

    queue->count--;

    return queue->data[queue->count];
}

/*
    優先度付きキューが空かどうか調べる
*/
bool priority_queue_is_empty(PriorityQueue queue)
{
    return queue->count == 0;
}



/*
    エラーチェック付きの malloc関数
*/
void* xmalloc(size_t size)
{
    void* p = malloc( size );
    if( p == NULL ){
        fputs( "メモリ割り当てに失敗しました。", stderr );
        exit( EXIT_FAILURE );
    }
    return p;
}

今度は、ソート済みの状態を保つ必要があるので、追加の処理が複雑になっていて、O(n) の計算量になります。一方、要素を取り出す処理は簡単で、O(1) で実現できます。

先に、要素を取り出す処理を考えてから作った方がいいかもしれません。優先度が最も高い要素が、配列の末尾側に来るように作るのがポイントで、こうすることで、要素の取り出しが末尾側で起こるので、残される要素をずらす作業をしなくて済みます。ずらす作業が入ると、計算量も O(1) から O(n) に悪化してしまいます。


参考リンク


------------------------------------------------------------------------

更新履歴

'2014/12/14 新規作成。



第10章のメインページへ

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

Programming Place Plus のトップページへ



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