優先度付きキュー

優先度付きキューはデータを入れているリストの中から優先度の高いものから順に要素を取り出すデータ構造. 優先度付きキューは抽象的なデータ型であり、実装によって挙動が異なる.基本的に優先度順に取り出されるが、同一の優先度のデータがある場合にどのように振る舞うかは実装に依る.多くの場合はヒープを用いて実装されるため取り出し順序は不定. 仮に通常のHeap実装を行った場合には、挿入削除がO(logN)、データ構造の構築がO(N)となる.また先に述べたように、同一優先度においては取り出し順序は不定となる. 一方でPairing Heap等を用いれば、同一優先度のデータに対しては取り出し順序をFIFOにすることができる.Paring Heapは実装が用意で高速と言われる.

優先度キューは様々な場面で使用される. ・ダイクストラ法 ・ハフマン符号 ・離散イベントシミュレーション 等