先頭へ戻る

優先度付きキュー | Programming Place Plus 用語集

Programming Place Plus トップページ用語集

先頭へ戻る

名称

解説

追加する要素に優先度(プライオリティ)を持たせ、優先度が高いものから取り出すように動作する抽象データ型のことです。

微妙に異なる呼び名がさまざま存在しますが、優先度(優先順位、プライオリティ)という部分が重要な意味をもちます。「キュー(待ち行列)」という言葉が付いていますが、通常のキューのように先入れ先出し(FIFO: First-In First-Out)の動作にはならず、取り出される順序は、優先度によって決定されます。

優先度には、追加するデータそのものを使う方法や、データとは別に指定する方法が考えられます。

優先度付きキューを実装する方法として、ヒープ二分探索木連結リスト配列を使うものなどいくつか選択肢があります。連結リストや配列を用いる場合、つねに優先度の順番どおりにソートしておく方法と、取り出すときに優先度が高いものを探す方法とが考えられます。方法によって、要素の追加や削除、参照の計算量に違いがあります。全体的に性能が良いヒープが用いられることが多いです。

優先度付きキューの解説が、アルゴリズムとデータ構造編【データ構造】第10章にあります。

優先度の順番どおりに取り出されることを利用して、ソートの方法として使えます。たとえば、整数のデータがいくつかあり、データそのものが優先度として機能するとすれば、適当な順番で優先度付きキューに入れたあと、すべて取り出すと、ソート済みのデータ列になっています。優先度付きキューがヒープを使って実装されているのなら、これはヒープソートそのものです。

C++ の場合

C++ の標準ライブラリには、優先度付きキューを実装した std::priority_queue があります(C++編【標準ライブラリ】第12章)。


参考リンク

更新履歴


用語集のトップページへ

Programming Place Plus のトップページへ



はてなブックマーク に保存 Pocket に保存 Facebook でシェア
Twitter でツイート Twitter をフォロー LINE で送る
rss1.0 取得ボタン RSS 管理者情報 プライバシーポリシー