RSS
追加する要素に優先度（プライオリティ）を持たせ、優先度が高いものから取り出すように動作する抽象データ型のことです。
微妙に異なる呼び名がさまざま存在しますが、優先度（優先順位、プライオリティ）という部分が重要な意味をもちます。「キュー（待ち行列）」という言葉が付いていますが、通常のキューのように先入れ先出し（FIFO: First-In First-Out）の動作にはならず、取り出される順序は、優先度によって決定されます。
優先度には、追加するデータそのものを使う方法や、データとは別に指定する方法が考えられます。
優先度付きキューを実装する方法として、ヒープや二分探索木、連結リスト、配列を使うものなどいくつか選択肢があります。連結リストや配列を用いる場合、つねに優先度の順番どおりにソートしておく方法と、取り出すときに優先度が高いものを探す方法とが考えられます。方法によって、要素の追加や削除、参照の計算量に違いがあります。全体的に性能が良いヒープが用いられることが多いです。
優先度付きキューの解説が、アルゴリズムとデータ構造編【データ構造】第１０章にあります。
優先度の順番どおりに取り出されることを利用して、ソートの方法として使えます。たとえば、整数のデータがいくつかあり、データそのものが優先度として機能するとすれば、適当な順番で優先度付きキューに入れたあと、すべて取り出すと、ソート済みのデータ列になっています。優先度付きキューがヒープを使って実装されているのなら、これはヒープソートそのものです。
C++ の標準ライブラリには、優先度付きキューを実装した std::priority_queue があります（C++編【標準ライブラリ】第１２章）。
Programming Place Plus のトップページへ
| はてなブックマーク に保存 | Pocket に保存 | Facebook でシェア |
| X で ポスト／フォロー | LINE で送る | noteで書く |
|
RSS
|
管理者情報 | プライバシーポリシー |