優先度付きキュー
優先度付きキュー（ゆうせんどつき -、英: priority queue）は、以下の4つの操作をサポートする抽象データ型である。
キューに対して要素を優先度付きで追加する。
最も高い優先度を持つ要素をキューから取り除き、それを返す。
(オプション) 最も高い優先度を持つ要素を取り除くことなく参照する。
(オプション) 指定した要素を取り除くことなく優先度を変更する。
出典: フリー百科事典『ウィキペディア（Wikipedia）』
優先度付きキューとは、その名の通り「優先度」という属性を持つキューのADTです（キューという名前ですが、必ずキューをベースに作られるADTという訳ではありません）。
優先度付きキューでは、キューに入った順番により取り出される通常のキューの FIFO とは異なり、優先度の高い要素が先に取り出されます。
例えば、以下のようなデータがあった場合、優先度付きキューは優先度の一番高い「50」を取り出します（逆に優先度の最も低い「100」を先に取り出すという考え方もあります）。
| 要素 | 優先度 |
|---|---|
| 100 | 1 |
| 20 | 2 |
| 50 | 4 |
| 10 | 3 |
優先度付きキューを例えば配列で考えた場合は、データの一番最初から探索を行い優先度の高い要素を探すので、\( O (N) \) の計算量になります。平衡2分探索木を用いれば、\( O ( \log N) \) の計算量になります。
この優先度付きキューを実装するために、より効率的なADTとして、ヒープがあり、優先度の最も高い要素の取得が\( O (1) \) で行えます。
優先度付きキューの操作
優先度付きでのデータの挿入
キューに対して、優先度付きでデータを挿入します。優先度に従い、ヒープの再構成が行われます。
優先度の最も高いデータの取り出し
キューの中から、最も優先度の高いデータを取り出します。取り出したデータは、キューから失われ、ヒープの再構成が行われます。
優先度の最も高いデータの確認
キューの中で、最も優先度の高いデータを確認します。データはキューから失われず、ヒープの再構成も行われません。
優先度付きキューとソート
優先度付きキューは、そのままソートにつながります。
ソートしたい要素をすべて優先度付きキューに入れてから順番に取り出すことで、要素をソートすることができます。
ヒープを使ったソートをヒープソートと言います。
ヒープソート (heap sort) とはリストの並べ替えを二分ヒープ木を用いて行うソートのアルゴリズムである[2]（ヒープ領域とは無関係であることに注意する）。
出典: フリー百科事典『ウィキペディア（Wikipedia）』
