Linux Programming

キュー

今回は簡単な例題として「キュー (queue)」という基本的なデータ構造を作ってみましょう。

●キューとは？

たとえばチケットを買う場合、カウンタの前に並んで順番を待たなくてはいけません。キューはカウンタの前に並ぶ行列と考えてください。列の先頭にいる人から順番にチケットを買うことができますが、あとから来た人は列の後ろに並ばなくてはいけません。列の先頭まで進むと、チケットを購入することができます。これを表したのが下図です。

         図 : キューの動作

このように、キューはデータを取り出すときは列の先頭から行い、データを追加するときは列の後ろへ行います。このため、キューは「待ち行列」とか「先入れ先出し (FIFO : first-in, first-out)」と呼ばれます。

●リングバッファよるキューの実装

キューは配列を使って簡単に実現できます。先頭位置を示す front と末尾を示す rear を用意し、front と rear の間にあるデータをキューに格納されているデータとするのがポイントです。次の図を見てください。

                  図 : キューの動作

まずキューは空の状態で、rear, front ともに 0 です。データの追加は、rear が示す位置にデータを書き込み、rear の値を +1 します。データ 10, 20, 30 を追加すると、図のようにデータが追加され rear は 3 になります。このとき front は 0 のままなので、先頭のデータは 10 ということになります。

次に、データを取り出す場合、front の示すデータを取り出しから front の値を +1 します。この場合、front が 0 なので 10 を取り出して front の値は 1 となり、次のデータ 20 が先頭になります。データを順番に 20, 30 と取り出していくと、3 つしかデータを書き込んでいないので当然キューは空になります。このとき front は 3 になり rear と同じ値になります。このように、front と rear の値が 0 の場合だけが空の状態ではなく、front と rear の値が等しくなると、キューは空になることに注意してください。

rear, fornt ともに値は増加していく方向なので、いつかは配列の範囲をオーバーします。このため、配列を先頭と末尾がつがっているリング状と考えて、rear, front が配列の範囲を超えたら 0 に戻すことにします。これを「循環配列」とか「リングバッファ」と呼びます。一般に、配列を使ってキューを実装する場合は、リングバッファとするのが普通です。

●キューの定義

それでは実際にプログラムを作ってみましょう。最初に、基本的な操作関数を説明します。今回はプログラムを簡単にするため、キューに格納するデータは浮動小数点数 (double) に限定します。

キュー (Queue) は構造体を使って定義します。

リスト : Queue の定義

typedef struct {
  int front, rear, count, size;
  double *buff;
} Queue;

メンバ変数 count はキューに格納されたデータ数をカウントします。この変数を用意することで、キューの状態を簡単にチェックすることができます。buff がキューの本体（配列）です。大きさはメンバ変数 size に格納します。

●キューの生成

リスト : キューの生成

Queue *make_queue(int n)
{
  Queue *que = malloc(sizeof(Queue));
  if (que != NULL) {
    que->front = 0;
    que->rear = 0;
    que->count = 0;
    que->size = n;
    que->buff = malloc(sizeof(double) * n);
    if (que->buff == NULL) {
      free(que);
      return NULL;
    }
  }
  return que;
}

関数 make_queue はキューを生成します。引数 n がキューの大きさです。関数 malloc で Queue のメモリを確保します。メンバ変数 front, rear, count は 0 で初期化します。あとは malloc でバッファの本体を取得して、que->buff にセットするだけです。

●データの挿入

次はデータを追加する関数 enqueue を作ります。

リスト : キューにデータを追加する

// キューは満杯か
bool is_full(Queue *que)
{
  return que->count == que->size;
}

// データの挿入
bool enqueue(Queue *que, double x)
{
  if (is_full(que)) return false;
  que->buff[que->rear++] = x;
  que->count++;
  if (que->rear == que->size)
    que->rear = 0;
  return true;
}

最初に関数 is_full を呼び出してキューが満杯かチェックします。is_full は que->count と que->size が等しいかチェックするだけです。キューが満杯であれば、enqueue は false を返します。データは que->rear の位置に格納し、q->count と q->rear の値を更新します。そして、q->rear の値が配列の範囲を超えたならば 0 に戻します。

●データの取り出し

次は、キューからデータを取り出す関数 dequeue を作ります。

リスト : キューからデータを取り出す

// キューは空か
bool is_empty(Queue *que)
{
  return que->count == 0;
}

// データを取り出す
double dequeue(Queue *que, bool *err)
{
  if (is_empty(que)) {
    *err = false;
    return 0;
  }
  double x = que->buff[que->front++];
  que->count--;
  *err = true;
  if (que->front == que->size)
    que->front = 0;
  return x;
}

まず、関数 is_empty を呼び出してキューにデータがあるかチェックします。is_empty は q->count が 0 かチェックするだけです。キューが空の場合、dequeue は *err に false をセットして 0 を返します。データがある場合は q->buff[q->front] の位置にあるデータを取り出します。あとは、q->count と q->front の値を更新し、q->front の値が配列の範囲を超えたら 0 に戻します。

あとの操作関数は簡単なので説明は割愛します。詳細は プログラムリスト1 をお読みくださいませ。

●実行例

これでプログラムは完成です。それでは、簡単な実行例を示しましょう。

リスト : 簡単なテスト

int main(void)
{
  Queue *que = make_queue(8);
  bool err;
  for (int i = 0; i < 4; i++)
    enqueue(que, i);
  printf("%d\n", queue_length(que));
  printf("%d\n", is_empty(que));
  printf("%d\n", is_full(que));
  while (!is_empty(que))
    printf("%.3f\n", dequeue(que, &err));
  printf("%d\n", queue_length(que));
  printf("%d\n", is_empty(que));
  printf("%d\n", is_full(que));
  for (int i = 0; i < 8; i++)
    enqueue(que, i);
  printf("%d\n", queue_length(que));
  printf("%d\n", is_empty(que));
  printf("%d\n", is_full(que));
  while (!is_empty(que))
    printf("%.3f\n", dequeue(que, &err));
  queue_delete(que);
  return 0;
}

$ clang queue1.c
$ ./a.out
4
0
0
0.000
1.000
2.000
3.000
0
1
0
8
0
1
0.000
1.000
2.000
3.000
4.000
5.000
6.000
7.000

make_queue でキューを作成して変数 que にセットします。for ループでキューにデータを 4 個セットします。queue_length の返り値は 4 で、is_empty と is_full の返り値はどちらも 0 (false) です。次に、while ループでキューにデータがある間、dequeue でデータを取り出します。先に入れたデータから順番に取り出されていることがわかります。

最後にデータを 8 個追加します。これでキューは満杯になるので、これ以上データを追加することはできません。is_full の返り値は 1 (true) になります。次に、dequeue でデータを取り出します。これでキューは空の状態になります。

●連結リストによるキューの実装

キューは連結リストを使っても簡単に実装することができますが、大きな欠点がひとつあります。連結リストをキューとして使う場合、データを追加するときに最後尾までセルをたどっていく操作が必要になるため、要素数が多くなるとデータの追加に時間がかかってしまうのです。

そこで、先頭のセルを参照する変数のほかに、最後尾のセルを参照する変数を用意します。こうすると、先頭からセルをたどらなくても、最後尾にデータを追加することができます。下図を見てください。

                       図 : キューの構造

この変数を front と rear としましょう。キューにデータがない場合は、(1) のように front と rear は NULL になっています。データがある場合は、(2) のように front は先頭のセルを参照し、rear は最後尾のセルを参照しています。これで、データの追加を効率的に行うことができます。

今回はセル (Cell) を直接操作してキューを作ってみましょう。定義するメソッドを下表に示します。

●キューの定義と生成

プログラムは次のようになります。

リスト : キューの定義

// セル
typedef struct cell {
  double item;
  struct cell *next;
} Cell;

// セルの生成
Cell *make_cell(double x, Cell *next)
{
  Cell *cp = malloc(sizeof(Cell));
  if (cp != NULL) {
    cp->item = x;
    cp->next = next;
  }
  return cp;
}

// キューの定義
typedef struct {
  Cell *front;
  Cell *rear;
} Queue;

// キューの生成
Queue *make_queue(void)
{
  Queue *que = malloc(sizeof(Queue));
  if (que != NULL)
    que->front = que->rear = NULL;
  return que;
}

構造体 Cell がセルを表します。メンバ変数 item のデータ型は double になります。関数 make_cell は新しいセルを生成して返します。キューは構造体 Queue で表します。関数 make_queue は malloc で Queue の本体を取得します。そして、メンバ変数 front と rear を NULL で初期化して、取得したメモリ que を返します。

●キューの廃棄

リスト : キューの廃棄

void delete_cell(Cell *cp)
{
  while (cp != NULL) {
    Cell *temp = cp->next;
    free(cp);
    cp = temp;
  }
}

void delete_queue(Queue *que)
{
  delete_cell(que->front);
  free(que);
}

キューの廃棄も簡単です。関数 delete_cell でセルを廃棄したあと、free でキューの本体 que を解放します。

●データの挿入 (2)

次はデータを挿入する関数 enqueue を作ります。

リスト : データの挿入

bool enqueue(Queue *que, double x)
{
  Cell *cp = make_cell(x, NULL);
  if (cp != NULL) {
    if (is_empty(que)) 
      que->front = que->rear = cp;
    else {
      que->rear->next = cp;
      que->rear = cp;
    }
    return true;
  }
  return false;
}

最初に make_cell で引数 x を格納するセルを生成します。生成できない場合は false を返します。次に、キューが空かチェックして、そうであれば、front と rear に新しいセル cp をセットします。キューが空でない場合、最後尾にデータを追加します。que->rear->next にセル cp セットして、最後尾のセルの後ろにつなげます。それから、que->rear を cp に書き換えて true を返します。

●データの取り出し (2)

次はデータを取り出す関数 dequeue を作ります。

リスト : データの取り出し

// キューは空か
bool is_empty(Queue *que)
{
  return que->front == NULL;
}

// キューからデータを取り出す
double dequeue(Queue *que, bool *err)
{
  if (is_empty(que)) {
    *err = false;
    return 0;
  }
  Cell *cp = que->front;
  double x = cp->item;
  *err = true;
  que->front = cp->next;
  free(cp);
  if (que->front == NULL) que->rear = NULL;
  return x;
}

最初に関数 is_empty でキューが空かチェックします。is_empty は que->front が NULL であれば true を返します。空の場合は *err に false をセットして 0 を返します。次に、先頭のセル que->front を cp に、cp->item を x に、*err の値を true にセットします。あとは、que->front の値を cp->next に書き換えてから、削除するセル cp を free で解放します。que->front が NULL ならば、que->rear も NULL に書き換えます。最後に return で x を返します。

あとのプログラムは簡単なので説明は割愛します。詳細は プログラムリスト２ をお読みください。

●実行例 (2)

それでは簡単な実行例を示します。

リスト : 簡単なテスト

int main(void)
{
  Queue *que = make_queue();
  bool err;
  for (int i = 0; i < 8; i++)
    enqueue(que, i);
  printf("%d\n", queue_length(que));
  printf("%d\n", is_empty(que));
  while (!is_empty(que))
    printf("%.3f\n", dequeue(que, &err));
  printf("%d\n", queue_length(que));
  printf("%d\n", is_empty(que));
  delete_queue(que);
  return 0;
}

$ clang queue2.c
$ ./a.out
8
0
0.000
1.000
2.000
3.000
4.000
5.000
6.000
7.000
0
1

キューに 0 から 7 まで enqueue で格納して dequeue でデータを取り出すと 0, 1, 2, 3, 4, 5, 6, 7 になります。データを入れた順番にデータが取り出されていることがわかります。

●プログラムリスト１

リスト : リングバッファによるキューの実装 (queue1.c)

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

// キューの定義
typedef struct {
  int front, rear, count, size;
  double *buff;
} Queue;

// キューの生成
Queue *make_queue(int n)
{
  Queue *que = malloc(sizeof(Queue));
  if (que != NULL) {
    que->front = 0;
    que->rear = 0;
    que->count = 0;
    que->size = n;
    que->buff = malloc(sizeof(double) * n);
    if (que->buff == NULL) {
      free(que);
      return NULL;
    }
  }
  return que;
}

// キューは満杯か
bool is_full(Queue *que)
{
  return que->count == que->size;
}

// キューは空か
bool is_empty(Queue *que)
{
  return que->count == 0;
}

// データの挿入
bool enqueue(Queue *que, double x)
{
  if (is_full(que)) return false;
  que->buff[que->rear++] = x;
  que->count++;
  if (que->rear == que->size)
    que->rear = 0;
  return true;
}

// データを取り出す
double dequeue(Queue *que, bool *err)
{
  if (is_empty(que)) {
    *err = false;
    return 0;
  }
  double x = que->buff[que->front++];
  que->count--;
  *err = true;
  if (que->front == que->size)
    que->front = 0;
  return x;
}

// 先頭データを参照する
double top(Queue *que, bool *err)
{
  if (is_empty(que)) {
    *err = false;
    return 0;
  }
  return que->buff[que->front];
}

// キューをクリアする
void clear(Queue *que)
{
  que->front = que->rear = que->count = 0;
}

// キューの個数を求める
int queue_length(Queue *que)
{
  return que->count;
}

// キューの削除
void queue_delete(Queue *que)
{
  free(que->buff);
  free(que);
}

// 簡単なテスト
int main(void)
{
  Queue *que = make_queue(8);
  bool err;
  for (int i = 0; i < 4; i++)
    enqueue(que, i);
  printf("%d\n", queue_length(que));
  printf("%d\n", is_empty(que));
  printf("%d\n", is_full(que));
  while (!is_empty(que))
    printf("%.3f\n", dequeue(que, &err));
  printf("%d\n", queue_length(que));
  printf("%d\n", is_empty(que));
  printf("%d\n", is_full(que));
  for (int i = 0; i < 8; i++)
    enqueue(que, i);
  printf("%d\n", queue_length(que));
  printf("%d\n", is_empty(que));
  printf("%d\n", is_full(que));
  while (!is_empty(que))
    printf("%.3f\n", dequeue(que, &err));
  queue_delete(que);
  return 0;
}

●プログラムリスト２

リスト : 連結リストによるキューの実装 (queue2.c)

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

// セル
typedef struct cell {
  double item;
  struct cell *next;
} Cell;

// セルの生成
Cell *make_cell(double x, Cell *next)
{
  Cell *cp = malloc(sizeof(Cell));
  if (cp != NULL) {
    cp->item = x;
    cp->next = next;
  }
  return cp;
}

// キューの定義
typedef struct {
  Cell *front;
  Cell *rear;
} Queue;

// キューの生成
Queue *make_queue(void)
{
  Queue *que = malloc(sizeof(Queue));
  if (que != NULL)
    que->front = que->rear = NULL;
  return que;
}

// キューの廃棄
void delete_cell(Cell *cp)
{
  while (cp != NULL) {
    Cell *temp = cp->next;
    free(cp);
    cp = temp;
  }
}

void delete_queue(Queue *que)
{
  delete_cell(que->front);
  free(que);
}

// キューは空か
bool is_empty(Queue *que)
{
  return que->front == NULL;
}

// データの挿入
bool enqueue(Queue *que, double x)
{
  Cell *cp = make_cell(x, NULL);
  if (cp != NULL) {
    if (is_empty(que)) 
      que->front = que->rear = cp;
    else {
      que->rear->next = cp;
      que->rear = cp;
    }
    return true;
  }
  return false;
}

// キューからデータを取り出す
double dequeue(Queue *que, bool *err)
{
  if (is_empty(que)) {
    *err = false;
    return 0;
  }
  Cell *cp = que->front;
  double x = cp->item;
  *err = true;
  que->front = cp->next;
  free(cp);
  if (que->front == NULL) que->rear = NULL;
  return x;
}

double top(Queue *que, bool *err)
{
  if (is_empty(que)) {
    *err = false;
    return 0;
  }
  return que->front->item;
}
  

void clear(Queue *que)
{
  delete_cell(que->front);
  que->front = que->rear = NULL;
}

int queue_length(Queue *que)
{
  int c = 0;
  for (Cell *cp = que->front; cp != NULL; cp = cp->next) c++;
  return c;
}

// 簡単なテスト
int main(void)
{
  Queue *que = make_queue();
  bool err;
  for (int i = 0; i < 8; i++)
    enqueue(que, i);
  printf("%d\n", queue_length(que));
  printf("%d\n", is_empty(que));
  while (!is_empty(que))
    printf("%.3f\n", dequeue(que, &err));
  printf("%d\n", queue_length(que));
  printf("%d\n", is_empty(que));
  delete_queue(que);
  return 0;
}

ヒープ

今回は簡単な例題として「ヒープ (heap)」という基本的なデータ構造を作ってみましょう。なお、ここでいう「ヒープ」はメモリの動的割り当てで使用する「ヒープ領域」とは違います。混同しないように注意してください。

●ヒープとは？

「ヒープ (heap)」は「半順序木 (partial ordered tree)」を配列で実現したデータ構造です。一般的な二分木では、親よりも左側の子のほうが小さく、親よりも右側の子が大きいという関係を満たすように作ります。半順序木の場合、親は子より小さいか等しいという関係を満たすように作ります。したがって、木の根（配列の添字 0）には、必ず最小値のデータが格納されます。下図にヒープと配列の関係を示します。

      図 : ヒープと配列の対応関係

ヒープを利用すると、最小値をすぐに見つけることができ、新しくデータを挿入する場合も、高々要素の個数 (n) の対数 (log₂ n) に比例する程度の時間で済みます。

●ヒープの構築 (1)

ヒープは、次の手順で作ることができます。

TABLE [＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊]     最初は空

      [80 ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊]     最初のデータをセット

      [80 10 ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊]     次のデータをセットし親と比較
       親 子                              親の位置 0 = (1 - 1)/2

      [10 80 ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊]     順序が違っていたら交換

      [10 80 60 ＊ ＊ ＊ ＊ ＊ ＊ ＊]     データをセットし比較
       親    子                           親の位置 0 = (2 - 1)/2

      [10 80 60 20 ＊ ＊ ＊ ＊ ＊ ＊]     データをセットし比較
          親    子                        親の位置 1 = (3 - 1)/2

      [10 20 60 80 ＊ ＊ ＊ ＊ ＊ ＊]     交換する

      ・・・・データがなくなるまで繰り返す・・・・


                図 : ヒープの構築 (1)

まず、データを最後尾に追加します。そして、このデータがヒープの条件を満たしているかチェックします。もしも、条件を満たしていなければ、親と子を入れ換えて、次の親をチェックします。これを木のルート方向 (添字 0 の方向) に向かって繰り返します。条件を満たすか、木のルート (添字 0) まで到達すれば、処理を終了します。これをデータの個数だけ繰り返します。

このアルゴリズムをそのままプログラムすると、次のようになります。

リスト : ヒープの構築

// ヒープの構築
void upheap(double *buff, int n)
{
  while (true) {
    int p = (n - 1) / 2;
    if (p < 0 || buff[p] <= buff[n]) break;
    double temp = buff[n];
    buff[n] = buff[p];
    buff[p] = temp;
    n = p;
  }
}

関数 upheap はヒープを満たすように n 番目の要素をルート方向に向かって移動させます。0 から n - 1 番目までの要素はヒープの条件を満たしているとします。n の親を p とすると、p は (n - 1) / 2 で求めることができます。そして、p が 0 より小さい、または buff[p] <= buff[n] であればヒープの条件を満たすので、break で処理を終了します。そうでなければ、buff[p] と buff[n] を交換して、次の親子関係をチェックします。

あとは、配列の最後尾にデータを追加して、upheap を呼び出せばいいわけです。また、データが格納されている配列でも、upheap を適用してヒープを構築することができます。

for (int i = 1; i < N; i++)
  upheap(buff, i)

N は配列の大きさを表すマクロです。ただし、この方法はデータ数を n とすると upheap を n - 1 回呼び出すため、それほど速い方法ではありません。もう少し高速な方法はあとで説明することにしましょう。

●ヒープの再構築

次に、最小値を取り出したあとで新しいデータを追加し、ヒープを再構築する手順を説明します。

TABLE [10 20 30 40 50 60 70 80 90 100]    ヒープを満たしている

      [＊ 20 30 40 50 60 70 80 90 100]    最小値を取り出す

      [66 20 30 40 50 60 70 80 90 100]    新しい値をセット

      [66 20 30 40 50 60 70 80 90 100]    小さい子と比較する
       ^  ^                               (2*0+1) < (2*0+2)
       親 子 子

      [20 66 30 40 50 60 70 80 90 100]    交換して次の子と比較
          ^     ^                         (2*1+1) < (2*1+2)
          親    子 子

      [20 40 30 66 50 60 70 80 90 100]    交換して次の子と比較
                ^        ^                (2*3+1) < (2*3+2)
                親       子 子            親が小さいから終了


                図 : ヒープの再構築

最初に、ヒープの最小値である添字 0 の位置にあるデータを取り出します。次に、その位置に新しいデータをセットし、ヒープの条件を満たしているかチェックします。ヒープの構築とは逆に、葉の方向 (添字の大きい方向) に向かってチェックしていきます。

まず、2 つの子の中で小さい方の子を選び、それと挿入したデータを比較します。もしも、ヒープの条件を満たしていなければ、親と子を交換し、その次の子供と比較します。これを、条件を満たすか、子供がなくなるまで繰り返します。このアルゴリズムをそのままプログラムすると次のようになります。

リスト : ヒープの再構築

void downheap(double *buff, int n, int size)
{
  while (true) {
    int c = 2 * n + 1;
    if (c >= size) break;
    if (c + 1 < size && buff[c] > buff[c + 1]) c++;
    if (buff[n] <= buff[c]) break;
    double temp = buff[n];
    buff[n] = buff[c];
    buff[c] = temp;
    n = c;
  }
}

関数 downheap はヒープを満たすように n 番目の要素を葉の方向へ移動させます。n + 1 番目から最後までの要素はヒープを満たしているとします。引数 size は配列の大きさを表します。次に、n の子 c を求めます。これが size よりも大きければ処理を終了します。そして、もう一つの子 (c + 1) がある場合は、小さい子を選択します。そして、buff[n] <= buff[c] が真であれば、ヒープの条件を満たしているので、break で処理を終了します。そうでなければ、n 番目と c 番目の要素を交換して処理を繰り返します。

最小値を取り出したあと新しいデータを挿入しない場合は、新しいデータの代わりに配列 buff の最後尾のデータを buff[0] にセットしてヒープを再構築します。上図の例でいえば、100 を buff[0] にセットして、ヒープを再構築すればいいわけです。この場合、ヒープに格納されているデータの個数は一つ減ることになります。

●ヒープの構築 (2)

ところで、n 個のデータをヒープに構築する場合、n - 1 回 upheap を呼び出さなければいけません。ところが、すべてのデータを配列に格納したあと、ヒープを構築するうまい方法があります。次の図を見てください。

TABLE [100 90 80 70 60|50 40 30 20 10]    後ろ半分が葉に相当

      [100 90 80 70|60 50 40 30 20 10]    60 を挿入する
                    ^
      [100 90 80 70|60 50 40 30 20 10]    子供と比較する
                    ^              ^       (2*4+1), (2*4+2)
                    親             子

      [100 90 80 70|10 50 40 30 20 60]    交換する

      ・・・ 70 80 90 を順番に挿入し修正する ・・・

      [100|10 40 20 60 50 80 30 70 90]    90 を挿入し修正した

      [100 10 40 20 60 50 80 30 70 90]    100 を挿入、比較
        ^  ^  ^                           (2*0+1), (2*0+2)
        親 子 子

      [10 100 40 20 60 50 80 30 70 90]    小さい子と交換し比較
           ^     ^  ^                     (2*1+1), (2*1+2)
           親    子 子

      [10 20 40 100 60 50 80 30 70 90]    小さい子と交換し比較
                 ^           ^  ^         (2*3+1), (2*3+2)
                 親          子 子

      [10 20 40 30 60 50 80 100 70 90]    交換して終了


                図 : ヒープの構築 (2)

配列を前半と後半の 2 つに分けると、後半部分はこれより下にはデータが繋がっていない葉の部分になります。つまり、後半部分の要素は互いに関係がなく、前半部分の枝にあたる要素と関係しているだけでなのです。したがって、後半部分だけを見れば、それはヒープを満たしていると考えることができます。

あとは、前半部分の要素に対して、葉の方向に向かってヒープの関係を満たすよう修正していけば、配列全体がヒープを満たすことになります。この処理は関数 downheap を使うと次のように簡単にプログラムできます。

for (int i = N / 2 - 1; i >= 0; i--)
    downheap(buff, x, N)

後ろからヒープを再構築していくと考えるとわかりやすいでしょう。この方法の場合、要素 n の配列に対して、n / 2 個の要素の修正を行えばよいので、最初に説明したヒープの構築方法よりも速くなります。

●優先度つき待ち行列

それでは、ヒープを使って「優先度つき待ち行列 (priority queue)」を作ってみましょう。一般に、キューは先入れ先出し (FIFO : first-in, first-out) のデータ構造です。キューからデータを取り出すときは、先に挿入されたデータから取り出されます。これに対し、優先度つき待ち行列は、データに優先度をつけておいて、優先度の高いデータから取り出していきます。

優先度つき待ち行列は、優先度を基準にヒープを構築することで実現できます。名前を Heap としましょう。今回はプログラムを簡単にするため、格納する要素のデータ型を浮動小数点数 (double) とします。Heap の操作関数を下表に示します。

メソッド名は enqueue, dequeue としてもよかったのですが、このプログラムでは push, pop としました。また、データを追加する関数を insert とし、最小値を取り出す関数を delete_min としている文献もあります。

●Heap の生成と廃棄

プログラムは次のようになります。

リスト : ヒープの定義

typedef struct {
  int size, limit;
  double *buff;
} Heap;

構造体 Heap のメンバ変数 size が格納している要素数、limit が配列の大きさを表します。buff が配列の本体です。Heap を生成する関数 make_heap は次のようになります。

リスト : ヒープの生成と廃棄

Heap *make_heap(int n)
{
  Heap *hp = malloc(sizeof(Heap));
  if (hp != NULL) {
    hp->size = 0;
    hp->limit = n;
    hp->buff = malloc(sizeof(double) * n);
    if (hp->buff == NULL) {
      free(hp);
      return NULL;
    }
  }
  return hp;
}

void delete_heap(Heap *hp)
{
  free(hp->buff);
  free(hp);
}

malloc で Heap の本体を確保し、メンバ変数 size を 0 に、limit を n に初期化します。それから配列本体を malloc で取得します。失敗した場合は heap を解放してから NULL を返します。最後に hp を返します。Heap を廃棄する関数 delete_heap も簡単です。配列本体を free で解放してから Heap の本体を解放します。

●データの挿入

次はデータを挿入する関数 push を作ります。

リスト : データの挿入

// ヒープは満杯か
bool is_full(Heap *hp)
{
  return hp->size == hp->limit;
}

// データの挿入
bool push(Heap *hp, double x)
{
  if (is_full(hp)) return false;
  hp->buff[hp->size] = x;
  upheap(hp->buff, hp->size);
  hp->size++;
  return true;
}

関数 is_full でヒープが満杯かチェックします。is_heap はメンバ変数 size と limit が等しいかチェックするだけです。データを挿入する場合、buff[hp->size] に x をセットしてから upheap を呼び出します。最後に size をインクリメントしてから true を返します。

●データの取り出し

次は、最小値を取り出す関数 pop を作ります。

リスト : データの取り出し

// ヒープは空か
bool is_empty(Heap *hp)
{
  return hp->size == 0;
}

// データの取り出し
double pop(Heap *hp, bool *err)
{
  if (is_empty(hp)) {
    *err = false;
    return 0;
  }
  double x = hp->buff[0];
  hp->buff[0] = hp->buff[--(hp->size)];
  downheap(hp->buff, 0, hp->size);
  *err = true;
  return x;
}

最初に is_empty でヒープが空かチェックします。is_empty はメンバ変数 size が 0 かチェックするだけです。空の場合は *err に false をセットして 0 を返します。データがある場合、配列の先頭要素を変数 x にセットします。次に、配列の末尾のデータを先頭に移動します。あとは downheap を呼び出してヒープを再構築するだけです。最後に *err に true をセットしてから return で x を返します。

あとのプログラムは簡単なので説明を割愛いたします。詳細は プログラムリスト３ をお読みください。

●実行例

それでは実際に実行してみましょう。次に示す簡単なテストを行ってみました。

リスト : 簡単なテスト

#define N 10

int main(void)
{
  double a[N] = {5,6,4,7,3,8,2,9,1,0};
  Heap *hp = make_heap(N);
  bool err;
  for (int i = 0; i < N; i++) {
    push(hp, a[i]);
    printf("%.3f ", peek(hp, &err));
  }
  printf("\n");
  printf("%d\n", is_empty(hp));
  printf("%d\n", is_full(hp));
  printf("%d\n", heap_length(hp));
  while (!is_empty(hp))
    printf("%.3f\n", pop(hp, &err));
  printf("%d\n", is_empty(hp));
  printf("%d\n", is_full(hp));
  printf("%d\n", heap_length(hp));
  delete_heap(hp);
  return 0;
}

実行結果は次のようになります。

$ clang heap.c
$ ./a.out
5.000 5.000 4.000 4.000 3.000 3.000 2.000 2.000 1.000 0.000
0
1
10
0.000
1.000
2.000
3.000
4.000
5.000
6.000
7.000
8.000
9.000
1
0
0

小さいデータから順番に取り出されていくことがわかります。

今回はここまでです。次回はヒープの応用例として「ヒープソート」と「マージソート」を取り上げる予定です。

●プログラムリスト３

リスト : ヒープ (heap.c)

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

// ヒープ
typedef struct {
  int size, limit;
  double *buff;
} Heap;

// ヒープの生成
Heap *make_heap(int n)
{
  Heap *hp = malloc(sizeof(Heap));
  if (hp != NULL) {
    hp->size = 0;
    hp->limit = n;
    hp->buff = malloc(sizeof(double) * n);
    if (hp->buff == NULL) {
      free(hp);
      return NULL;
    }
  }
  return hp;
}

// ヒープの廃棄
void delete_heap(Heap *hp)
{
  free(hp->buff);
  free(hp);
}

// ヒープの構築
void upheap(double *buff, int n)
{
  while (true) {
    int p = (n - 1) / 2;
    if (p < 0 || buff[p] <= buff[n]) break;
    double temp = buff[n];
    buff[n] = buff[p];
    buff[p] = temp;
    n = p;
  }
}

// ヒープの再構築
void downheap(double *buff, int n, int size)
{
  while (true) {
    int c = 2 * n + 1;
    if (c >= size) break;
    if (c + 1 < size && buff[c] > buff[c + 1]) c++;
    if (buff[n] <= buff[c]) break;
    double temp = buff[n];
    buff[n] = buff[c];
    buff[c] = temp;
    n = c;
  }
}

// ヒープは満杯か
bool is_full(Heap *hp)
{
  return hp->size == hp->limit;
}

// データの挿入
bool push(Heap *hp, double x)
{
  if (is_full(hp)) return false;
  hp->buff[hp->size] = x;
  upheap(hp->buff, hp->size);
  hp->size++;
  return true;
}

// ヒープは空か
bool is_empty(Heap *hp)
{
  return hp->size == 0;
}

// 要素数
int heap_length(Heap *hp)
{
  return hp->size;
}

// データの取り出し
double pop(Heap *hp, bool *err)
{
  if (is_empty(hp)) {
    *err = false;
    return 0;
  }
  double x = hp->buff[0];
  hp->buff[0] = hp->buff[--(hp->size)];
  downheap(hp->buff, 0, hp->size);
  *err = true;
  return x;
}

double peek(Heap *hp, bool *err)
{
  if (is_empty(hp)) {
    *err = false;
    return 0;
  }
  return hp->buff[0];
}

#define N 10

int main(void)
{
  double a[N] = {5,6,4,7,3,8,2,9,1,0};
  Heap *hp = make_heap(N);
  bool err;
  for (int i = 0; i < N; i++) {
    push(hp, a[i]);
    printf("%.3f ", peek(hp, &err));
  }
  printf("\n");
  printf("%d\n", is_empty(hp));
  printf("%d\n", is_full(hp));
  printf("%d\n", heap_length(hp));
  while (!is_empty(hp))
    printf("%.3f\n", pop(hp, &err));
  printf("%d\n", is_empty(hp));
  printf("%d\n", is_full(hp));
  printf("%d\n", heap_length(hp));
  delete_heap(hp);
  return 0;
}