RSS
トップページ – アルゴリズムとデータ構造編 – 【データ構造】第１０章
問題① 配列による優先度付きキューを「要素を格納するときには、特に気にせず格納処理を行い、要素を取り出すときに、優先度の高いものを探すという考え方」で実装してください。
本編のヒープによる実装と同じインターフェースを保つように作れば、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 新規作成。
Programming Place Plus のトップページへ
| はてなブックマーク に保存 | Pocket に保存 | Facebook でシェア |
| X で ポスト／フォロー | LINE で送る | noteで書く |
|
RSS
|
管理者情報 | プライバシーポリシー |