C言語で連結リストを使った優先度付きキューの実装方法

本記事では、整数値の「データ」と「優先度」が与えられたとき、指定された優先度に従って連結リスト（リンクリスト）を構築し、結果を表示する方法を解説します。

優先度付きキューとは

キューはFIFO（First In, First Out：先入れ先出し）方式のデータ構造であり、最初に挿入された要素が最初に取り除かれます。

一方、優先度付きキュー（プライオリティキュー）は、要素の挿入・削除を「優先度」に基づいて行えるキューの一種です。キュー、スタック、連結リストなどのデータ構造を用いて実装でき、以下のルールに従って動作します。

• 優先度が最も高いデータ（要素）は、優先度が低いものよりも先に処理される。
• 2つの要素が同じ優先度を持つ場合は、リストに追加された順序（先入れ先出し）で処理される。

ノードの構成

優先度付きキューを実装するための連結リストのノードは、次の3つの部分で構成されます。

• データ（data）：整数値を格納します。
• アドレス（next）：次のノードへのポインタ（アドレス）を格納します。
• 優先度（priority）：優先度を表す整数値を格納します。0〜10の範囲とし、0が最も高い優先度、10が最も低い優先度を表します。

実行例

入力：（データ, 優先度）のペアとして、(7, 1)、(1, 2)、(3, 3)、(2, 0) をこの順で挿入します。

出力：

2 7 1 3

優先度が最も高い「2（優先度0）」が最初に取り出され、以降は優先度の昇順（1 → 2 → 3）に出力されます。

アルゴリズム

開始
ステップ1：構造体 node を宣言する
　　data、priority を宣言する
　　struct node* next を宣言する
ステップ2：関数 Node* newNode(int d, int p)
　　Node* temp = (Node*)malloc(sizeof(Node)) を設定
　　temp->data = d を設定
　　temp->priority = p を設定
　　temp->next = NULL を設定
　　temp を返す
ステップ3：関数 int peek(Node** head)
　　(*head)->data を返す
ステップ4：関数 void pop(Node** head)
　　Node* temp = *head を設定
　　(*head) = (*head)->next を設定
　　temp を解放（free）する
ステップ5：関数 push(Node** head, int d, int p)
　　Node* start = (*head) を設定
　　Node* temp = newNode(d, p) を設定
　　もし (*head)->priority > p ならば、
　　　　temp->next = *head を設定
　　　　(*head) = temp を設定
　　そうでなければ
　　　　start->next != NULL かつ start->next->priority < p の間繰り返し
　　　　　　start = start->next を設定
　　　　temp->next = start->next を設定
　　　　start->next = temp を設定
ステップ6：関数 int isEmpty(Node** head)
　　(*head) == NULL を返す
ステップ7：関数 int main()
　　Node* pq = newNode(7, 1) を設定
　　push(&pq, 1, 2) を呼び出す
　　push(&pq, 3, 3) を呼び出す
　　push(&pq, 2, 0) を呼び出す
　　!isEmpty(&pq) の間繰り返し
　　　　peek(&pq) の結果を表示する
　　　　pop(&pq) を呼び出す
終了

C言語による実装コード

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

// 優先度付きキューのノード構造体
typedef struct node {
    int data;
    int priority;
    struct node* next;
} Node;

// 新しいノードを作成する
Node* newNode(int d, int p) {
    Node* temp = (Node*)malloc(sizeof(Node));
    temp->data = d;
    temp->priority = p;
    temp->next = NULL;
    return temp;
}

// 先頭のデータを参照する
int peek(Node** head) {
    return (*head)->data;
}

// 先頭の要素を削除する
void pop(Node** head) {
    Node* temp = *head;
    (*head) = (*head)->next;
    free(temp);
}

// 優先度に従って要素を挿入する
void push(Node** head, int d, int p) {
    Node* start = (*head);
    Node* temp = newNode(d, p);
    if ((*head)->priority > p) {
        // 新しいノードが最も優先度が高い場合、先頭に挿入
        temp->next = *head;
        (*head) = temp;
    } else {
        // 挿入位置を探す
        while (start->next != NULL &&
        start->next->priority < p) {
            start = start->next;
        }
        // リストの末尾、または適切な位置に挿入
        temp->next = start->next;
        start->next = temp;
    }
}

// キューが空かどうかを判定する
int isEmpty(Node** head) {
    return (*head) == NULL;
}

// main関数
int main() {
    Node* pq = newNode(7, 1);
    push(&pq, 1, 2);
    push(&pq, 3, 3);
    push(&pq, 2, 0);
    while (!isEmpty(&pq)) {
        printf("%d ", peek(&pq));
        pop(&pq);
    }
    return 0;
}

実行結果

2 7 1 3

まとめ

このように、連結リストを挿入時に優先度の昇順となるよう並べ替えておくことで、先頭から要素を取り出すだけで常に最も優先度の高いデータを取得できる優先度付きキューを実現できます。挿入にはO(n)の計算量が必要ですが、先頭参照・削除はO(1)で行えるのが特徴です。