Javaのデータ構造PriorityQueueの詳細解説

2年 ago
結衣, 春花
1 minute

PriorityQueueはJavaで使用される優先順位付きキューのデータ構造で、AbstractQueueクラスを継承しQueueインターフェースを実装しています。要素を取り出す際には、優先度が最も高い要素が常に取り出されるという特徴があります。

PriorityQueueは、ヒープ（Heap）を使用して実装されており、具体的には2分の最小ヒープ（Binary Min Heap）が使用されています。2分の最小ヒープでは、親ノードの値は常に子ノードの値よりも小さいか等しいです。これは、PriorityQueueから要素を取り出す際に、常にヒープのトップから取り出されるため、その要素が現在の最小の要素であるということを意味します。

PriorityQueueは、要素がComparableインターフェースを実装しているか、要素の優先度を比較するための比較器（Comparator）を提供する限り、任意の型の要素を格納できます。

PriorityQueueの例を作成する方法を以下に示します：

PriorityQueue<Integer> pq = new PriorityQueue<>();

上記のコードでは、Integer型のPriorityQueueを作成しました。

PriorityQueueに要素を追加する例のコードは以下の通りです：

pq.add(5);
pq.add(3);
pq.add(8);

上記のコードでは、add（）メソッドを使用してPriorityQueueに要素を追加します。要素を追加した後、PriorityQueueは要素の位置を自動的に調整してヒープの特性を維持します。

PriorityQueueから要素を取り出す例のコードは以下の通りです：

while (!pq.isEmpty()) {
    System.out.println(pq.poll());
}

上記のコードでは、PriorityQueueから要素を取り出して印刷するためにwhileループを使用しました。poll()メソッドを使用すると、ヒープの先頭の要素を取り出して削除できます。

PriorityQueueをカスタムの優先度で並べ替えたい場合、比較器を持つコンストラクタを使用してPriorityQueueを作成することができます。以下はサンプルコードです：

PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());

上記のコードでは、Collections.reverseOrder()を使用して逆順の比較器を作成し、その結果、PriorityQueueは降順でソートされます。

基本の追加や取り出し操作に加えて、PriorityQueueにはsize()メソッドで要素の数を返す他、peek()メソッドで先頭の要素を取得するが削除はされないなど、さまざまなメソッドが用意されています。

一般的に言って、PriorityQueueはJavaで非常によく使われるデータ構造であり、優先キューの機能を簡単に実装することができます。

bannerAds