1. 序章

このチュートリアルでは、優先キューとは何かを学び、それがどのように機能するかを理解します。 優先キューには、Dijkstraやスケジューリングアルゴリズムなどの他のアルゴリズムで多くのアプリケーションがあります。 優先度付きキューは、複数のプログラムとその実行を調整するシステムにとって非常に重要です（プログラムは優先度に基づいて実行するように選択されます）。 また、インターネットなどのネットワーキングシステムにとっても非常に重要です。これは、重要なデータに優先順位を付けて、データがより速く通過するようにするのに役立つためです。

2. 優先キュー

優先キューは、特殊なタイプのキューです。 各キューのアイテムには、priorityという追加情報があります。 通常のキューとは異なり、優先キューの値は、先入れ先出し（FIFO）ルールではなく、優先度に基づいて削除されます。 次の例は、値に最小から最大への順序が課された優先キューを示しています。ここでは、など。 アイテムの値を示します。 アイテムの優先度を示します。 したがって、この例で最も優先度の高いアイテムは（優先度1で）、最初に削除されます。 そして、最も優先度の低いアイテム（優先度19）は、プロセスの最後に削除されます。 このチュートリアルでは、他の情報をキューの要素に簡単に添付できるため、今後はアイテムの値として優先度を使用します。優先度付きキューの主な操作は次のとおりです。

  • 追加：キューにアイテムを追加します
  • ピーク：ノードを削除せずに、キュー内の最も優先度の高いアイテムを返します
  • remove：キュー内の最も優先度の高いアイテムを削除して返します

2.1. 優先キューの特性

優先キューは、次の特性を含むキューの拡張です。

  • 優先キュー内のすべての要素には、それに関連付けられた優先度値があります
  • 優先度の高い要素が一番上に移動され、最初に削除されます
  • 優先キュー内の2つの要素の優先度が同じである場合、FIFOの原則を使用して配置されます。

2.2. 優先キューの種類

優先キューには次の2つのタイプがあります。

  • 最小優先度キュー：最小優先度キューでは、優先度の低い番号が高い優先度として指定されます。
  • 最大優先度キュー：最大優先度キューでは、優先度の高い番号が優先度の高いものとして指定されます。

どちらのタイプでも、優先キューは要素のコレクションを格納し、常に最も「極端な」要素を提供できます。これは、優先キューから値を抽出する唯一の方法です。 このチュートリアルの残りの部分では、最大優先度キューについて説明します。 最小優先度キューは類似しています。

3. 実装

優先キューを実装するには、さまざまな方法があります。 主な方法には、配列、リンクリスト、バイナリ検索ツリー（BST）、およびバイナリヒープツリーが含まれます。 ヒープデータ構造は、優先キューを実装するための最も効率的な方法です。 ヒープデータ構造を深く掘り下げる前に、キューの基本的な操作に関する各実装アプローチの効率について簡単に説明しましょう。

3.1. ヒープデータ構造

バイナリヒープは、次のプロパティを持つバイナリツリーの一種です（ただし、バイナリ search ツリーではありません）。

  • すべてのノードの値は、その子に格納されているすべての値よりも大きい（または小さい）必要があります
  • これは完全なツリーであり、可能な限り最小の高さを持っていることを意味します

このチュートリアルでは、最大ヒープの例を使用します。 ヒープ構造をよりよく理解するために、次の例を調べてみましょう。各ノードについて、左の子はになり、右の子はになります。 親はになります（のルートノードを除く）。  ヒープデータ構造のより詳細な概要については、ヒープソートをJavaで説明している記事を読むことができます。

3.2. 優先キュー操作

優先キューで実行できる一般的な操作には、挿入、削除、およびピークが含まれます。 バイナリヒープを使用して、最大優先度キューを維持します。 ヒープのルートにあるアイテムは、すべての要素の中で最も優先度が高くなります。 バイナリヒープに新しいノードを追加する場合は、新しいノードが追加された後も、ヒープの2つのプロパティが維持されるようにする必要があります。 最初に、優先キューの最後に新しいアイテムを挿入します。 親ノードよりも大きいことが判明した場合、要素が交換されます。 このプロセスは、新しいアイテムが正しい位置に配置されるまで続きます。 挿入プロセスを理解するために例を見てみましょう。 優先度付きキューに追加すると、次のようになります。親よりも大きいことに気付いたので、それらを交換します。次に、新しい親よりもまだ大きいので、交換します。その親なので、停止して優先キューに到達します。次のコードは、挿入関数の詳細を示しています。

次に、優先キューから最大要素を削除できます。 ご存知のように、ルートノードは最大ヒープ内で最も優先度の高いアイテムです。 ルートノードを削除するときは、優先キューの最後のアイテムに置き換えます。 次に、このアイテムは子ノードと比較され、大きい方のノードと交換されます。 ヒーププロパティが復元されるまで、ツリーを下に移動し続けます。 それでは、このプロセスがどのように機能するかを理解するために例を適用してみましょう。 まず、ルートノードを最後のアイテムに置き換えます。新しい優先度キューは、ルートノードがその子よりも小さい最大ヒープのプロパティに違反します。次に、ノードがリーフに到達するか、それよりも大きくなるまで、ノードを大きい子と交換します。両方の子：これで、の子よりも大きくなり、停止して優先キューに到達します。次のコードは、削除機能の詳細を示しています。

ヒープ内の最大のノードをすばやく確認したい場合、それは簡単です。 ルートへのポインタを返すだけです。

3.4. 時間計算量分析

挿入の場合、ヒープデータ構造全体をヒープ化する必要がある場合があります。 したがって、挿入プロセスにはO（1）時間しかかかりませんが、ヒープ化プロセスにはがかかります。 同じことが削除にも当てはまります。 最大優先度の値がどこにあるかはわかっていますが、ヒープの再作成にはまだ時間がかかります。 バイナリヒープは常に完全なツリーを保証するため、これらは最悪の場合の効率が保証されます。優先キューから値を抽出する時間の複雑さは、ヒープのルートノードを確認するだけでよいためです。

4. 優先キューのアプリケーション

優先キューは、実際のシステムだけでなく、他のアルゴリズムにも広く適用されています。 主なアプリケーションは次のとおりです。

  • アルゴリズム：特定の基本的なアルゴリズムは、ダイクストラの最短パスアルゴリズム、プリムのアルゴリズム、ヒープソートアルゴリズムなどの優先度付きキューに依存しています。
  • データ圧縮：ハフマンコードなどのデータ圧縮技術で使用されます
  • オペレーティングシステム： 優先キューは、実行する次のプロセスを選択するために使用され、優先度の高いタスクが優先度の低いタスクよりも先に実行されるようにします。 。 また、負荷分散や割り込み処理にも適用されます
  • 帯域幅管理：優先キューは重要なデータパケットに優先順位を付けるために使用されるため、ネットワークはこれらのパケットができるだけ早く宛先に到達することを確認できます。

5. 結論

この記事では、優先キューと呼ばれるデータ構造について説明しました。優先キューの定義と特性を学習しました。 ヒープデータ構造を使用して優先キューを実装する方法を学びました。 最後に、優先キューの操作の複雑さと優先キューの適用について説明しました。