C/C++で学ぶ優先度付きキュー（プライオリティキュー）の基本と実装

優先度付きキュー（プライオリティキュー）とは、要素に割り当てられた「優先度」に従って挿入・削除が行われる特殊なキューの一種です。優先度は0〜10の整数値で表現され、0が最も高い優先度、10が最も低い優先度を意味します。病院の救急外来で重症患者が待ち順序に関係なく先に診察されるように、重要度の高いタスクを優先的に処理したい場面で活躍するデータ構造です。

優先度付きキューを守る2つの基本ルール

優先度付きキューを実装する際には、次の2つのルールに従います。

• 優先度の高い要素ほど先に処理される — 最も優先度の高いデータは、優先度の低いデータよりも先に実行されます。
• 同じ優先度なら追加順に処理される — 2つの要素が同じ優先度を持つ場合、リストに追加された順序どおりに処理されます。

実装に利用できるデータ構造

優先度付きキューは、スタック、キュー、連結リストなど、さまざまなデータ構造を用いて実装できます。本記事では、その中でもキューのデータ構造を使った実装方法を詳しく解説します。キューによる実装には、大きく分けて次の2つのアプローチがあります。

方法1：単一の配列で複数の優先度別キューを管理する

1つ目の方法は、優先度ごとに個別のキューを用意し、それらを1つの配列に格納する方式です。各キューはFront（先頭）とRear（末尾）という2つのポインタを持ちます。

• Rearポインタ：要素の挿入位置を示し、要素が挿入されるたびに1ずつ増加します。
• Frontポインタ：要素の削除位置を示し、要素が削除されるたびに1ずつ減少します。

さらに、この2つのポインタの位置関係から、キュー内に存在する要素数を求めることも可能です。

ただし、この方式には注意点があります。新しい要素を挿入するための空きスペースを確保する際にポインタや要素のシフトが必要となるため、時間計算量と空間計算量の両面でコストが高くなりやすいという欠点があります。

方法2：各優先度ごとのキューを循環配列として管理する

2つ目の方法では、優先度ごとに独立したキュー（配列）を作成します。各キューは循環配列（リングバッファ）として実装され、ここでもFrontとRearの2つのポインタ変数を使用します。

• 指定された優先度番号を持つ要素は、その番号に対応するキューへ挿入されます。
• 削除を行う場合は、必ず最も優先度の高いキューから要素を取り出します。
• 優先度を表す整数値は小さいほど優先度が高く、最小値の0が最高優先度を示します。

補足： 各キューのサイズがすべて同じであれば、複数の1次元配列を個別に作成する代わりに、1つの2次元配列としてまとめて管理することもできます。

挿入（Insert）操作のアルゴリズム

指定された優先度のキューへデータを挿入する擬似コードは以下のとおりです。最初にオーバーフロー（満杯）のチェックを行い、Rearポインタを進めてからデータを格納します。

insert(queue, data, priority)
    IF (queue->Rear[priority] = MAX-1 AND queue->Front[priority] = 0) OR (queue->Rear[priority] + 1 = queue->Front[priority])
        Print Overflow
    END
    IF queue->Rear[priority - 1] = MAX-1
        Set queue->Rear[priority - 1] = 0
    ELSE
        Set queue->Rear[priority] = queue->Rear[priority - 1] + 1
    END
    Set queue->CQueue[priority - 1][queue->Rear[priority - 1]] = data
    IF queue->Front[priority - 1] = -1
        Set queue->Front[priority - 1] = 0
END

削除（Delete）操作のアルゴリズム

削除操作では、優先度0から順にキューを走査し、最初に見つかった要素（＝最も優先度の高い要素）を取り出します。どのキューにも要素が存在しない場合は、アンダーフローとして処理します。

delete(queue)
    Set flag = 0, priority = 0
    WHILE priority <= MAX-1
        IF NOT queue->Front[priority] = -1
            Set flag = 1
            Set value = queue->CQueue[priority][queue->Front[priority]]
            IF queue->Front[priority] = queue->Rear[priority]
                Set queue->Front[priority] = queue->Rear[priority] = -1
            ELSE
                IF queue->Front[priority] = MAX-1
                    Set queue->Front[priority] = 0
                ELSE
                    Set queue->Front[priority] = queue->Front[priority] + 1
                END
            END
            Break
        END
        Set priority = priority + 1
    END
    IF flag = 0
        Print underflow
    ELSE
        Return value
    END
END

まとめ

優先度付きキューは、「優先度の高いものから順に処理する」という要件を実現するための基本的かつ重要なデータ構造です。本記事で紹介したように、配列とFront/Rearポインタを組み合わせれば、C言語でも比較的シンプルに実装できます。なお、C++では標準テンプレートライブラリ（STL）の std::priority_queue を利用すれば、ヒープ構造に基づいた効率的な優先度付きキューを簡単に扱えるため、実務ではこちらの活用も検討するとよいでしょう。