algorithm - プライオリティ キューはいつ使用しますか?

Question

私が知っているプラ​​イオリティ キューを使用する唯一の例は、ダイクストラのアルゴリズム (最小コストを計算するため) です。

他にどのような場面で役に立ちますか？

Answer 1

ビジネスアプリケーションの実用的な例を次に示します。

あなたは病院を経営していて、患者がやって来ます。スタッフには医師が 1 人しかいません。最初の男が入ってきて、すぐに配膳されました。次に、風邪をひいた男性がやって来て、助けを求めます。あなたが彼をキューに追加すると、彼は医者が利用できるようになるのを待ちます。次に、頭に斧を持った男がドアから入ってきます。彼はより高い医療責任を負っているため、より高い優先順位が割り当てられています。それで、風邪をひいた男は列に並んで押し倒されます。次に、呼吸に問題のある人がやってきます。ということで、またもや風邪をひいた男が優先的に倒される。これは現実世界ではトリアージと呼ばれますが、この場合は医療ラインです。

これをコードに実装すると、プライオリティ キューとワーカー スレッド (医師) を使用して、消耗品/作業単位 (患者) で作業を実行します。

Answer 2

ヒープに基づく優先キューは、入力シーケンスを部分的にソートしています。これには、mcdowella がいくつかの例を示したように、シーケンス全体が必要ない場合にすぐに並べ替えるよりも利点があります。特に、n 個の要素のうち m 個だけが必要な場合は、O(m log n) の複雑さがあります。2 つ目の利点は、要素を動的に追加する場合、つまり事前にシーケンス全体がわからない場合です。ヒープをバッキング ストレージとして使用すると、別の要素を追加する方が、並べ替えられたシーケンスに挿入するよりも高速になります。

さらに、ソートされた順序で単一の要素をポップし、それらを破棄する場合 (つまり、後でソートされたシーケンスが必要ない場合)、優先キューを使用すると、リーダーに正しいメッセージが与えられます。また、ヒープに基づくものや事前に入力シーケンスをソートするものなど、さまざまな実装を簡単に交換できます。これは好みの問題ですが、任意のシーケンスを使用して常に同じ結果を得ることができますが、これはコードを読みにくくするだけです。

Answer 3

統計の大規模なコレクションをスキャンして上位 N 個の項目を報告しています - N 個の最もビジーなネットワーク接続、N 個の最も価値のある顧客、N 個の最大ディスク ユーザー...

Answer 4

プライオリティ キュー (最小/最大ヒープ) の多くのアプリケーションがあります。しかし、古典的で有名なアルゴリズムを探している場合、たとえば、加重無向グラフの最小スパニング ツリーを見つけるPrim のアルゴリズムでは、優先キューが使用されます。