- @ThothChildren
- 2018.9.17
- PV 102
優先度付きキュー
ー 概要 ー
優先度付きキューはデータを入れているリストの中から優先度の高いものから順に要素を取り出すデータ構造.抽象的なデータ型であり、実装によって挙動が異なる.基本的に優先度順に取り出されるが、同一の優先度のデータがある場合にどのように振る舞うかは実装による.多くの場合はヒープを用いて実装されるため取り出し順序は不定.
この章を学ぶ前に必要な知識
条件
- それぞれに優先度を持つデータ
効果
- 優先度に基づいてデータを取り出す
- 複数のデータをリストの形式で保持して貯めておく
ポイント
- ヒープで実装することが多く、通常のヒープでは同優先度を持つデータに対しては取り出し順序は不定
- 基本は優先度で取り出し、同一の優先度があるときの取り出し順序はキューのようなFIFOとは限らない
解 説
優先度付きキューはデータを入れているリストの中から優先度の高いものから順に要素を取り出すデータ構造.
優先度付きキューは抽象的なデータ型であり、実装によって挙動が異なる.基本的に優先度順に取り出されるが、同一の優先度のデータがある場合にどのように振る舞うかは実装に依る.多くの場合はヒープを用いて実装されるため取り出し順序は不定.
仮に通常のHeap実装を行った場合には、挿入削除がO(logN)、データ構造の構築がO(N)となる.また先に述べたように、同一優先度においては取り出し順序は不定となる.
一方でPairing Heap等を用いれば、同一優先度のデータに対しては取り出し順序をFIFOにすることができる.Paring Heapは実装が用意で高速と言われる. | 優先度付きキューとは |
優先度キューの中にデータを追加するときとデータを取りだすときの様子. | |
優先度キューは様々な場面で使用される.
・ダイクストラ法
・ハフマン符号
・離散イベントシミュレーション
等 | 優先度キューの使用例 |
この章を学んで新たに学べる
Comments