Java プライオリティ キュー: 従来のキューではありません

この記事では、Queue インターフェイスを実装するプライオリティ キュー、Java クラスについて学びます。プログラマーは通常のキュー インターフェイスについて何を知っていますか? まず第一に、このインターフェイスは FIFO 原理、つまり「先入れ先出し」に基づいています。これは、一般的な意味での通常の行列を思い出させます。マックドライブでコーヒーを買いたいですか？自分の車が窓際の先頭にいる場合は、次のドライバーよりも先にコーヒーを受け取ることができます。

キューインターフェース宣言

public interface Queue<E> extends Collection<E>

プライオリティキューとは何ですか

プライオリティキューとは何ですか? まずは後ろから要素を挿入したり、先頭から要素を削除したりする場合のQueueインターフェースを実装したクラスです。しかし、店内はいつもの行列ではありません。Java 優先キュー要素の順序は、要素の優先順位によって異なります。最も優先度の高い要素がキューの先頭に移動されます。最高ランクの要素を削除 (提供) すると、2 番目の要素がコーヒーを取得するために先頭に移動します。優先順位はどのように決まるのでしょうか? ドキュメントによると、優先キューの要素は、使用されるコンストラクターに応じて、自然な順序に従って、またはキュー構築時に提供されるコンパレーターによって順序付けされます。優先度の最小ヒープに基づく優先度のキュー。つまり、数値キュー要素の場合、キューの最初の要素は、これらの数値の最小値になります。多くの場合、この定義を読んだ後、新人学生は優先キューが線形的にソートされていると考え始めます。つまり、要素が自然数であるキューを使用する場合、最初の要素が最小となり、最後の要素が最大になります。これは完全に真実ではありません。プライオリティ キューが実際にどのように機能し、それが何をもたらすかを理解するには、ヒープがどのように機能するかを理解する必要があります。プライオリティ キューの内部構造については、後で例を使用して説明します。次に、その外部属性について詳しく見てみましょう。その場合、最初の要素が最小となり、最後の要素が最大になります。これは完全に真実ではありません。プライオリティ キューが実際にどのように機能し、それが何をもたらすかを理解するには、ヒープがどのように機能するかを理解する必要があります。プライオリティ キューの内部構造については、後で例を使用して説明します。次に、その外部属性について詳しく見てみましょう。その場合、最初の要素が最小となり、最後の要素が最大になります。これは完全に真実ではありません。プライオリティ キューが実際にどのように機能し、それが何をもたらすかを理解するには、ヒープがどのように機能するかを理解する必要があります。プライオリティ キューの内部構造については、後で例を使用して説明します。次に、その外部属性について詳しく見てみましょう。

PriorityQueue クラスのコンストラクターと宣言

PriorityQueue クラスは、Java で優先キューを構築するための 6 つの異なる方法を提供します。

• PriorityQueue() - 要素を自然な順序に従って順序付けする、デフォルトの初期容量 (11) を持つ空のキュー。
• PriorityQueue(Collection c) - 指定されたコレクション内の要素を含む空のキュー。
• PriorityQueue(int initialCapacity) - 要素を自然な順序に従って順序付けする、指定された初期容量を持つ空のキュー。
• PriorityQueue(int initialCapacity, Comparator コンパレータ) - 指定されたコンパレータに従って要素を順序付けする、指定された初期容量を持つ空のキュー。
• PriorityQueue(PriorityQueue c) - 指定された優先キュー内の要素を含む空のキュー。
• PriorityQueue(SortedSet c) - 指定されたソートセット内の要素を含む空のキュー。

Java の優先キューは次の方法で宣言されます。

public class PriorityQueue<E> extends AbstractQueue<E> implements Serializable

PriorityQueueの作成

整数の優先キューを作成しましょう。優先キューの実装、Java コード:

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

引数なしで優先キューを作成しました。この場合、優先キューの先頭はキューの最小番号となる。ヘッドを削除すると、次に小さな要素がその場所を占めます。したがって、要素をキューから昇順で削除できます。必要に応じて、Comparator インターフェイスを使用して順序付けの原則を変更できます。

Java PriorityQueue メソッド

PriorityQueue Java クラスには、要素を追加、削除、確認するための重要なメソッドがあります。

要素を優先キューに挿入する

• boolean add(object) は、指定された要素を優先キューに挿入します。成功した場合は true を返します。キューがいっぱいの場合、メソッドは例外をスローします。
• boolean offer(object) は、指定された要素をこの優先キューに挿入します。キューがいっぱいの場合、メソッドは false を返します。

どちらの加算操作も使用できますが、ほとんどの場合に違いはありません。以下は、優先キューへの要素の開始と追加の小さな例です。

import java.util.PriorityQueue;
import java.util.Queue;
public class Priority2 {
    public static void main(String[] args) {
        Queue<Integer> priorityQueue1 = new PriorityQueue<>();
        for (int i = 5; i > 0; i--) {
            priorityQueue1.add(i);
        }
        System.out.println(priorityQueue1);
    priorityQueue1.offer(0);
        System.out.println(priorityQueue1);
    }
}

出力は次のとおりです。

[1, 2, 4, 5, 3]
[0, 2, 1, 5, 3, 4]

要素の順序がおかしいようですが、後で説明します。

優先キューからの要素の取得と削除

• boolean Remove(object) は、指定された要素の単一のインスタンスが存在する場合、このキューからそれを削除します。
• オブジェクトpoll()は、このキューの先頭を取得して削除します。キューが空の場合は null を返します。
• void clear() は、優先キューからすべての要素を削除します。
• Object element() は、このキューの先頭を削除せずに取得します。キューが空の場合はNoSuchElementExceptionをスローします。
• オブジェクト Peak() は、キューの先頭を削除せずに取得します。キューが空の場合は null を返します。

import java.util.PriorityQueue;
import java.util.Queue;
 
public class Priority2 {
    public static void main(String[] args) {
        Queue<Integer> priorityQueue = new PriorityQueue<>();
        //put 5 elements to the queue using add
        for (int i = 5; i > 0; i--) {
            priorityQueue.add(i);
        }
        System.out.println("the head of the queue = " + priorityQueue.peek());
        //removing element by element from the queue using poll and print it out
        while (!priorityQueue.isEmpty()) {
            System.out.println(priorityQueue.poll());
        }
        //put 5 new elements into the empty queue using offer
        for (int i = 10; i > 5; i--) {
            priorityQueue.offer(i);
        }
        System.out.println("now the head of the queue = " + priorityQueue.peek());
        System.out.println("the queue before removing 9:");
        System.out.println(priorityQueue);
        priorityQueue.remove(9);
        System.out.println("the queue after removing 9:");
        System.out.println(priorityQueue);
        //removing all the elements from the queue
        priorityQueue.clear();
        System.out.println(priorityQueue);
        //trying to print out the head of the empty Queue using peek - we'll get null
        System.out.println(priorityQueue.peek());
        //trying to print out the head of the empty Queue using element - we'll get the exception
        System.out.println(priorityQueue.element());
    }
}

出力：

the head of the queue = 1
1
2
3
4
5
now the head of the queue = 6
the queue before removing 9:
[6, 7, 9, 10, 8]
the queue after removing 9:
[6, 7, 8, 10]
[]
null
Exception in thread "main" java.util.NoSuchElementException
  at java.base/java.util.AbstractQueue.element(AbstractQueue.java:136)
  at Priority2.main(Priority2.java:32)

ご覧のとおり、 element() メソッドを使用して空のキューの先頭を出力しようとすると、NoSuchElementExceptionが発生します。

PriorityQueue コンパレータ

• コンパレータ comparator() は、キュー内の要素を順序付けるために使用されるコンパレータを返します。キューがその要素の自然な順序に従って並べ替えられている場合は、null を返します。

Java 優先キュー、コンパレータを使用した例

上記のコード例では自然な (昇順) 順序を使用しましたが、場合によっては変更する必要があります。これは Java 優先キューの例です。ここでは、Comparator インターフェイスを実装する独自の内部コンパレータ クラスを作成します。コンパレーターは要素を最大から最小の順に並べ替えます。

import java.util.PriorityQueue;
import java.util.Comparator;
 
class Priority3 {
    public static void main(String[] args) {
        // Creating a priority queue with myComparator
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new MyComparator());
        for (int i = 5; i > 0; i--) {
            priorityQueue.add(i);
        }
        System.out.println("the head of Queue = " + priorityQueue.peek());
        while (!priorityQueue.isEmpty()) {
            System.out.println(priorityQueue.poll());
        }
    }
}
 
class MyComparator implements Comparator<Integer> {
    @Override
    public int compare(Integer number1, Integer number2) {
        int value = number1.compareTo(number2);
        //sorting elements from maximal to minimal
        if (value > 0) {
            return -1;
        } else if (value < 0) {
            return 1;
        } else {
            return 0;
        }
    }
}

出力：

the head of Queue = 5
5
4
3
2
1

Queue の先頭は最小要素ではなく最大要素になり、順序が逆に変更されました。

イテレータを使用した PriorityQueue の反復処理

ProrityQueue は Collection フレームワークの一部であり、Iterable<>インターフェイスを実装します。優先キューの要素を反復するには、iterator()メソッドを使用できます。以下に例を示します。

import java.util.PriorityQueue;
import java.util.Iterator;
import java.util.Queue;
 
class Priority4 {
   public static void main(String[] args) {
       // Creating a priority queue
       Queue<Integer> priorityQueue = new PriorityQueue<>();
       //put 5 elements to the queue using add
       for (int i = 5; i > 0; i--) {
           priorityQueue.add(i);
       }
       //Iterating via iterator() method
       Iterator<Integer> iterator = priorityQueue.iterator();
       while (iterate.hasNext()) {
           System.out.print(iterator.next() + " ");
       }
   }
}

出力：

1 2 4 5 3 

その他の PriorityQueue メソッド

• boolean contains(Object o) は、 キューに o 要素が含まれる場合に true を返します。
• int size() は、このキュー内の要素の数を返します。
• Object[] toArray() は、このキュー内のすべての要素を含む配列を返します。

以下に例を示します。

import java.util.PriorityQueue;
import java.util.Queue;
 
public class Priority5 {
   public static void main(String[] args) {
       Queue<Integer> priorityQueue = new PriorityQueue<>();
       for (int i = 5; i > 0; i--) {
           priorityQueue.offer(i);
       }
 
       System.out.println("our queue: " + priorityQueue);
 
       System.out.println("Does our queue contain 8?  " + priorityQueue.contains(8));
       System.out.println("Does queue contain 5?  " + priorityQueue.contains(5));
 
       System.out.println("The quantity of queue elements: " + priorityQueue.size());
       Object[] myArray = priorityQueue.toArray();
       System.out.println("print out our array:");
       for (Object name : myArray) {
           System.out.println(name);
       }
   }
}

出力：

our queue: [1, 2, 4, 5, 3]
Does our queue contain 8?  false
Does our queue contain 5?  true
The quantity of queue elements: 5
print out our array:
1
2
4
5
3

PriorityQueue Java 8 定義

priorityqueue Java 8 ドキュメントを開くと、次の定義が見つかります。それは、優先度ヒープに基づく無制限の優先度キューです。優先キューの要素は、使用されるコンストラクターに応じて、自然な順序に従って、またはキューの構築時に提供されるコンパレーターによって順序付けされます。優先キューでは null 要素は許可されません。自然順序付けに依存する優先キューでは、比較不可能なオブジェクトの挿入も許可されません (挿入すると ClassCastException が発生する可能性があります)。ここでヒープは非常に重要な単語です。ここでは、Priority Queue 要素の順序付けのプロパティについて説明します。

PriorityQueue の動作原理: バイナリ ヒープ

例から始めましょう。Queue インターフェイスを実装する 2 つのオブジェクトを作成しましょう。そのうちの 1 つは LinkedList、2 つ目は PriorityQueue です。どちらも整数の 5 つの要素 (1、2、3、4、および 5) を持っており、要素を最大のものから最小のものまでキューに入れ始めます。したがって、最初は 5、次に 4、3、2、そして最後のものは 1 になります。次に、両方のリストを印刷して順序を確認します。

   Queue<Integer> queueL = new LinkedList<>();
       for (int i = 5; i > 0; i--) {
           queueL.add(i);
       }
       System.out.println("LinkedList Queue (FIFO): " + queueL);
       Queue<Integer> priorityQueue = new PriorityQueue<>();
 
       for (int i = 5; i > 0; i--) {
       priorityQueue.offer(i);
       }
       System.out.println("PriorityQueue: " + priorityQueue)

これらのコードが動作した結果は次のようになります。

LinkedList Queue (FIFO): [5, 4, 3, 2, 1]
PriorityQueue: [1, 2, 4, 5, 3]

まあ、リンクリストの順序は予測可能であり、理解可能です。FIFO 原理に従って順序付けされます。5 から始めたので、この要素は行の一番最初にあり、次に 4 と続きます。優先キューの順序について何が言えるでしょうか? ドキュメントによると、優先キューの要素は、自然な順序に従って、またはキューの構築時に提供されるコンパレーターによって順序付けされます。ただし、この順序は線形ソートの意味では「自然」ではないようです。[1, 2, 4, 5, 3] ではなく、[1, 2, 3, 4, 5] を期待します。取得順序がこのようになる理由を理解するには、ヒープに基づく優先キューを思い出してください。ヒープとは何ですか? 二分木に基づいたデータ構造です。ヒープの主な特性: 各親の優先順位がその子の優先順位よりも高くなります。各親に 2 つ以下の子があり、レベルの塗りつぶしが上から下 (同じレベル、つまり左から右) に行われる場合、ツリーは完全なバイナリと呼ばれることを思い出してください。バイナリ ヒープは、要素が追加または削除されるたびに自身を再編成します。min-heap の場合、挿入順序に関係なく、最小の要素がルートに移動します。この最小ヒープに基づく優先キュー。つまり、キュー要素が数値の場合、キューの最初の要素はこれらの数値の最小値になります。ルートを削除すると、次に小さいものがルートになります。

私たちの例に戻ってみましょう。

ステップ 1.優先キューに「5」を入れます。根になってしまうのです。 ステップ 2.優先キューに「4」を追加します。4 <5 なので、新しい要素は古い要素よりも大きくなるはずです。4 はルートになり、5 はその左の子になります。Java のデータ構造は [4, 5] になります。 ステップ 3.「3」を追加します。一時的にルート(4)の右側の子になります。ただし、3 < 4 なので、引き上げる必要があります。3 と 4 を交換します。これで、[3, 5, 4] のような構造ができました。 ステップ 4.「2」を追加します。5.2<5の左の子になるので交換します。2 は 3 の左の子になるため、2 < 3 なので、交換処理がもう 1 回行われます。これで、構造 [2,3,4,5] ができました。 ステップ 5。「1」を追加します。3 の右の子から 2 の左の子に至り、ルートに進みます。結果のデータ構造: [1,2,4,5,3] 削除プロセスはルートから開始され、逆の手順が引き起こされます。したがって、最初にルートとして 1 があり、次に 2、3、4、そして最後に 5 があります。そのため、削除操作 poll() を使用します。

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

線形センスの出力が「ソート」されました。

1
2
3
4
5

したがって、一部の操作では優先キューが効果的である可能性があります。各要素の挿入と削除には O(log N) 時間がかかり、O(1) で最小限の要素を取得できます。完全な例は次のとおりです。

import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
 
public class PriorityQueueExample {
   public static void main(String[] args) {
 
       Queue<Integer> queueL = new LinkedList<>();
       for (int i = 5; i > 0; i--) {
           queueL.add(i);
       }
       System.out.println("Print our LinkedList Queue (FIFO): " + queueL);
       Queue<Integer> priorityQueue = new PriorityQueue<>();
 
       for (int i = 5; i > 0; i--) {
       priorityQueue.offer(i);
       }
 
       System.out.println("PriorityQueue printing (by iterating, no elements removing): " + priorityQueue);
       System.out.println("Print PriorityQueue using poll() (by retrieval): " );
       while (!priorityQueue.isEmpty()) {
           System.out.println(priorityQueue.poll());
       }
}
}
Print our LinkedList Queue (FIFO): [5, 4, 3, 2, 1]
PriorityQueue printing (by iterating, no elements removing): [1, 2, 4, 5, 3]
Print our  PriorityQueue using poll() (by retrieval): 
1
2
3
4
5

優先キューはバイナリ ヒープに基づいているため、要素が線形に並べ替えられた順序に保たれないことを理解することが重要です。根から葉までのすべての方法は順序付けられていますが、根からの別の方法は順序付けられていません。つまり、キューの最小限の要素を非常に迅速に取得できるということです。

優先キューについて知っておくべきこと。簡単なリスト

• 優先キューでは NULL オブジェクトは許可されません。
• PriorityQueue には同等のオブジェクトのみを追加できます。
• 優先キューは、バイナリ ツリーの一種である最小ヒープとして構築されます。最小要素はルートです。優先キューのオブジェクトは、デフォルトでは自然な順序で並べられます。
• カスタム注文が必要な場合は、Comparator を使用できます。
• PriorityQueue はスレッド セーフではないため、同時環境で作業するには PriorityBlockingQueue を使用することをお勧めします。
• PriorityQueue は、追加メソッドとポーリング メソッドに O(log(n)) 時間を提供し、最小限の要素を取得するのに O(1) 時間を提供します。