トップページ – アルゴリズムとデータ構造編 – 【データ構造】第10章
問題① 配列による優先度付きキューを「要素を格納するときには、特に気にせず格納処理を行い、要素を取り出すときに、優先度の高いものを探すという考え方」で実装してください。
本編のヒープによる実装と同じインターフェースを保つように作れば、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;
};
/*
優先度付きキューを作る
*/
(size_t size)
PriorityQueue priority_queue_create{
struct PriorityQueue_tag* queue = xmalloc( sizeof(struct PriorityQueue_tag) );
->data = malloc( sizeof(int) * size );
queue->count = 0;
queue->size = size;
queue
return queue;
}
/*
優先度付きキューを削除する
*/
void priority_queue_delete(PriorityQueue queue)
{
( queue->data );
free( queue );
free}
/*
優先度付きキューに要素を入れる
*/
void priority_queue_enqueue(PriorityQueue queue, int value)
{
( queue->count + 1 < queue->size );
assert
->data[queue->count] = value;
queue->count++;
queue}
/*
優先度付きキューから要素を取り出す
*/
int priority_queue_dequeue(PriorityQueue queue)
{
( !priority_queue_is_empty(queue) );
assert
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] ){
= queue->data[i];
min = i;
min_index }
}
// 取り出した要素の後続を詰めなおすと遅いので、
// 末尾の要素と入れ替えることで、削除を実現する。
// この後、queue->count がデクリメントされるので、
// 交換先の要素は、新たな要素が追加されない限り、参照されることは無い。
(int, queue->data[min_index], queue->data[queue->count - 1]);
SWAP
->count--;
queue
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 ){
( "メモリ割り当てに失敗しました。", stderr );
fputs( EXIT_FAILURE );
exit}
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;
};
/*
優先度付きキューを作る
*/
(size_t size)
PriorityQueue priority_queue_create{
struct PriorityQueue_tag* queue = xmalloc( sizeof(struct PriorityQueue_tag) );
->data = malloc( sizeof(int) * size );
queue->count = 0;
queue->size = size;
queue
return queue;
}
/*
優先度付きキューを削除する
*/
void priority_queue_delete(PriorityQueue queue)
{
( queue->data );
free( queue );
free}
/*
優先度付きキューに要素を入れる
*/
void priority_queue_enqueue(PriorityQueue queue, int value)
{
( queue->count + 1 < queue->size );
assert
if( queue->count == 0 ){
->data[0] = value;
queue}
else{
size_t i;
for( i = queue->count; i >= 1 && queue->data[i - 1] < value; --i ){
->data[i] = queue->data[i - 1];
queue}
->data[i] = value;
queue}
->count++;
queue}
/* 優先度付きキューから要素を取り出す */
int priority_queue_dequeue(PriorityQueue queue)
{
( !priority_queue_is_empty(queue) );
assert
->count--;
queue
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 ){
( "メモリ割り当てに失敗しました。", stderr );
fputs( EXIT_FAILURE );
exit}
return p;
}
今度は、ソート済みの状態を保つ必要があるので、追加の処理が複雑になっていて、O(n) の計算量になります。一方、要素を取り出す処理は簡単で、O(1) で実現できます。
先に、要素を取り出す処理を考えてから作った方がいいかもしれません。優先度がもっとも高い要素が、配列の末尾側に来るように作るのがポイントで、こうすることで、要素の取り出しが末尾側で起こるので、残される要素をずらす作業をしなくて済みます。ずらす作業が入ると、計算量も O(1) から O(n) に悪化してしまいます。
新規作成。
Programming Place Plus のトップページへ
はてなブックマーク に保存 | Pocket に保存 | Facebook でシェア |
X で ポスト/フォロー | LINE で送る | noteで書く |
RSS | 管理者情報 | プライバシーポリシー |