C言語で優先度付きキューを実装する。

はじめに

C 言語での優先度付きキュー（Priority Queue）の設計と実装について説明します。

優先度付きキューとは

優先度付きキューは、キーと値のペアを格納するデータ構造です。キーには優先度が設定されており、値はそのキーに対応するデータです。優先度付きキューは、キーの値が大きい順にデータを取り出すことができます。

仕組み

優先度付きキューは、二分木を使って実装されます。二分木は、各ノードにおいて、親ノードよりも小さい値を持つノードは左に、大きい値を持つノードは右に配置される木構造です。
こうすることで、データの挿入や取り出しの計算量が O(log(n)) で行えます。

データ構造

優先度付きキューのデータ構造は以下です。

typedef struct PgNode PgNode;
struct PgNode {
  int id;
  float priority;
  PgNode *left;
  PgNode *right;
};

typedef struct PriorityQueue PriorityQueue;
struct PriorityQueue {
  PgNode *root;
  int size;
};

PgNode は二分木のノードを表します。root には二分木の根が入ります。size は優先度付きキューの要素数です。

初期化

優先度付きキューの初期化は以下のように実装します。

PriorityQueue *new_priority_queue() {
  PriorityQueue *queue = malloc(sizeof(PriorityQueue));
  queue->root = NULL;
  queue->size = 0;
  return queue;
}

root は NULL で初期化します。size は 0 で初期化します。

追加

優先度付きキューに要素を追加する関数を以下に示します。

static PgNode *new_pg_node(int id, float priority) {
  PgNode *node = malloc(sizeof(PgNode));
  node->id = id;
  node->priority = priority;
  node->left = NULL;
  node->right = NULL;
  return node;
}

static void push_node(PgNode **head, PgNode *node) {
  if (*head == NULL) {
    *head = node;
    return;
  }

  if ((*head)->priority < node->priority) {
    push_node(&(*head)->right, node);
  } else {
    push_node(&(*head)->left, node);
  }
}

void push_priority_queue(PriorityQueue *queue, int id, float priority) {
  PgNode *node = new_pg_node(id, priority);
  push_node(&queue->root, node);
  queue->size++;
}

新しいノードを作成し、優先度に応じて適切な位置に挿入します。

取り出し

優先度付きキューから要素を取り出す関数を以下に示します。

void pop_priority_queue(PriorityQueue *queue, int *result_id,
                        float *result_priority) {
  // If the queue is empty, return.
  if (queue->root == NULL) {
    return;
  }

  // Find the maximum priority node.
  PgNode *parent = NULL;
  PgNode *node = queue->root;
  while (node->right) {
    parent = node;
    node = node->right;
  }

  *result_id = node->id;
  *result_priority = node->priority;

  // Remove the maximum priority node.
  if (parent == NULL) {
    queue->root = node->left;
  } else {
    parent->right = node->left;
  }

  free(node);
  queue->size--;
}

最大の優先度を持つノードを探し、そのノードを取り出します。
取り出したノードの左のノードを親ノードの右に接続し、取り出したノードを解放します。

メモリの解放

優先度付きキューのメモリを解放する関数を以下に示します。

static void free_pg_node(PgNode *node) {
  if (node) {
    free_pg_node(node->left);
    free_pg_node(node->right);
    free(node);
  }
}

void free_priority_queue(PriorityQueue *queue) {
  free_pg_node(queue->root);
  free(queue);
}

再帰関数を使って、全てのノードを解放します。

まとめ

C 言語で優先度付きキューを実装する方法について説明しました。優先度付きキューは、二分木を使って実装され、挿入や取り出しの計算量が O(log(n)) で行えます。今回の実装では、最大の優先度を持つノードを取り出す関数を実装しました。他にも、最小の優先度を持つノードを取り出す関数を実装することもできます。