IT資格用語解説基本情報技術者試験・データ構造の種類
優先度付きキュー
更新日:
用語解説
優先度付きキューは、要素を優先度と一緒に格納し、取り出すときは追加した順番ではなく、優先度が最も高い要素から取り出すデータ構造です。
■ 試験で押さえるポイント
通常のキューは先入れ先出し（FIFO）ですが、優先度付きキューは優先度の高い順に取り出します。同じ優先度の要素は、先に追加したものから取り出すのが一般的です（問題文の定義を確認します）。
主な操作は、要素の追加（enqueue）、最も優先度の高い要素の取出し（dequeue）、要素数の取得（size）です。
実装には、優先度ごとにキューを分ける方法や、ヒープ（親の値が子の値以下になるように保つ2分木）を使う方法があります。ヒープを使うと、追加と取出しをどちらも で行えます。
OSのプロセスを優先度の順に実行するスケジューリングや、最短経路を求めるダイクストラ法などで使われます。
例: 優先度は1、2、3で、小さい値ほど優先度が高いものとします。
操作 | 取り出した要素 | 操作後のキュー（要素:優先度） |
|---|---|---|
enqueue("P", 2) | P:2 | |
enqueue("Q", 1) | P:2, Q:1 | |
enqueue("R", 2) | P:2, Q:1, R:2 | |
dequeue() | Q（優先度1） | P:2, R:2 |
dequeue() | P（優先度2で先に追加） | R:2 |
enqueue("S", 1) | R:2, S:1 | |
dequeue() | S（優先度1） | R:2 |
■ 選択肢での判断ポイント
トレースでは、操作のたびにキューの中身を「優先度」と「追加した順」で書き出します。dequeueでは、優先度が最も高い要素のうち一番早く追加された要素を取り除きます。戻り値を使わないdequeueでも要素は取り除かれる点に注意します。