PriorityQueue Java コレクション フレームワークの優先キュー

この記事では、java に関する関連知識を提供します。主に、PriorityQueue 優先キューに関する関連知識を紹介します。Java コレクション フレームワークは、PriorityQueue と PriorityBlockingQueue の 2 種類の優先順位を提供します。レベル キュー、PriorityQueue はスレッドです。安全ではありません、PriorityBlockingQueue はスレッドセーフです。一緒に見てみましょう。皆さんのお役に立てれば幸いです。

推奨学習: 「java ビデオ チュートリアル 」

Java コレクション フレームワークには、2 種類の PriorityQueue と PriorityBlockingQueue が用意されています。 priority queue, PriorityQueue is thread-unsafe, and PriorityBlockingQueue is thread-safe. この記事では主に PriorityQueue

について紹介します Java コレクション フレームワークにおける priorityQueue の関係は次のとおりです。

##1. PriorityQueue 使用時の注意点

1. 使用する場合は、PriorityQueue が配置されているパッケージ、つまり

をインポートする必要があります。

import java.util.PriorityQueue

2.

PriorityQueue に配置された要素はサイズを比較できる必要があり、比較できないオブジェクトは比較できません。挿入できない場合、 ClassCastException## がスローされます。
#3. Null オブジェクトは挿入できません。そうでない場合は、NullPointerException がスローされます。

4. 容量制限はありません。 、任意の数の要素を挿入でき、内部容量は自動的に拡張できます

5 。要素の挿入と削除の

時間計算量は、対数 2 を底とします n

6. PriorityQueue の最下層はヒープ データ構造を使用します

7. デフォルトの PriorityQueue は小さなヒープです ---つまり、毎回取得される要素は最小の要素です (

必要な場合大きなヒープにするには、メソッドを再比較する必要があります。デフォルトの比較メソッドは、Comparable インターフェイスの CompareTo メソッドです)

2. PriorityQueue の共通インターフェイスの概要

1. Priority Queue の構築

ここでは

PriorityQueue

の一般的な構築方法をいくつか紹介しますが、その他についてはヘルプ ドキュメントを参照してください。

コンストラクターPriorityQueue()デフォルトの容量は 11PriorityQueue(intInitialCapacity)初期容量は、initialCapacityPriorityQueue(Collection extends E> c)##PriorityQueue(Comparator comparator)##PriorityQueue(int initialCapacity, Comparator comparator)#、指定されたコンパレータ

関数の紹介

空の優先キューを作成する,

#を作成します。

優先キュー、注: initialCapacity を 1 より小さくすることはできません。それ以外の場合は、IllegalArgumentException がスローされます。 Often

コレクションを使用して優先キューを作成します

デフォルトの初期容量で優先キュー を作成し、その要素

を 指定されたコンパレータ # と比較します。

初期容量は#initialCapacity#を作成します## の優先キュー

に従ってその要素を比較します。注:<strong> </strong>initialCapacity は 1 未満にはできません。そうでない場合は、IllegalArgumentException がスローされます。 Often

2. PriorityQueue の要素の比較

構築方法を読んだ後、もう一度質問を考えてみましょう

プライオリティ キューはどのようにして順序を達成するのでしょうか?プライオリティ キューは小さなルート ヒープを利用して実装されるため、

#小さなルート ヒープを実装するプロセスでは、要素の比較が必要であることがわかっているため、PriorityQueue 内の要素はでは、PriorityQueue はどのようにして要素を比較するのでしょうか?

PriorityQueue は、

Comparble と Comparator の 2 つのメソッドを採用します。

1.

Comparble はデフォルトの内部比較メソッド です。ユーザーがカスタム タイプ オブジェクトを挿入する場合、オブジェクトは Comparble インターフェイスを実装し、compareTo メソッド ## をオーバーライドする必要があります。 #2. ユーザーはコンパレータ オブジェクトの使用を選択することもできます。ユーザー

がカスタム タイプ オブジェクトを挿入する場合は、コンパレータ クラスを提供する必要があり、そのクラスは Comparator インターフェイスを実装してオーバーライドする必要があります。比較方法。

プログラムがここでエラーを報告していることがわかります。なぜでしょうか?挿入した Child オブジェクトは比較できないため (

は Comparable インターフェイスを実装しておらず、カスタム コンパレータを使用していません)

ご覧のとおり、

つまり、Comparable インターフェイスで CompareTo メソッドを使用します。これは、デフォルトの比較メソッドです。

#現時点では、これがデフォルトの比較メソッドです。 、もう一度エラーを見てみましょう。 情報

PriorityQueue に要素を挿入するときに問題があるようです

次に、 PriorityQueue のソースコードを見てみましょう (以下は PriorityQueue の Offer メソッドのソースコードです)

shiftUp のソースコードを見てくださいもう一度

#siftUpComparable でクリックを続ける

ここで、 PriorityQueue. カスタム コンパレータがなく、Comparable インターフェイスが実装されていません。,

もちろん、エラーが報告されます。

それでは、Child クラスに Comparable インターフェイスを実装して、年齢別に比較してみましょう。

import java.util.PriorityQueue;
class Child implements Comparable<Child>{
    int age;
    String name;

    public Child(int age, String name) {
        this.age = age;
        this.name = name;
    }

    @Override
    public int compareTo(Child o) {
        return this.age - o.age;  // 默认实现小根堆
    }

    @Override
    public String toString() {
        return "Child{" +
                "age=" + age +
                ", name='" + name + '\'' +
                '}';
    }
}
public class TestPriorityQueue {
    public static void main(String[] args) {
        PriorityQueue<Child> priorityQueue = new PriorityQueue<>();

        priorityQueue.offer(new Child(12, "小亮"));
        priorityQueue.offer(new Child(11, "小红"));
        priorityQueue.offer(new Child(8, "小强"));
        System.out.println(priorityQueue);
    }
}

# 上記では Compable インターフェイスを実装しましたが、年齢コンパレータをカスタマイズしたらどうなるでしょうか?

class Child {
    int age;
    String name;

    public Child(int age, String name) {
        this.age = age;
        this.name = name;
    }

    @Override
    public String toString() {
        return "Child{" +
                "age=" + age +
                ", name='" + name + '\'' +
                '}';
    }
}
class AgeComparator implements Comparator<Child> {

    @Override
    public int compare(Child o1, Child o2) {
        return o1.age - o2.age; // 实现小根堆
        // return o2.ae - o1.age 实现大根堆
    }
}
public class TestPriorityQueue {
    public static void main(String[] args) {
        AgeComparator ageComparator = new AgeComparator();
        // 创建具有默认初始容量的 PriorityQueue ，并根据指定的比较器对其元素进行排序。
        PriorityQueue<Child> priorityQueue = new PriorityQueue<>(ageComparator);
        // 可以看到这里我的Child对象虽然没有实现Comparable接口，但因为我们对Child对象自定义了一个年龄比较器，所以插入元素不会报错
        priorityQueue.offer(new Child(12, "小亮"));
        priorityQueue.offer(new Child(11, "小红"));
        priorityQueue.offer(new Child(8, "小强"));
        System.out.println(priorityQueue);
    }
}

3. 最も優先度の高い要素の挿入/削除/取得

関数名関数の紹介boolean Offer(E e)最高の優先順位の要素を削除し、優先キューが空の場合、戻ります。 return null有効な要素の数を取得 clear()Clearboolean

要素 e を挿入し、挿入が成功した場合は true を返します。 e オブジェクトは空であり、NullPointerException をスローします。時間の複雑さ、注意: スペースが十分でない場合、拡張されます。最高の優先順位、優先キューが空の場合、nullを返します	Epoll()
	int size()
	void
isEmty()	優先キューが空かどうかを確認し、空の場合は返します。 empty true
推奨学習: 「 Java ビデオ チュートリアル 」

以上がPriorityQueue Java コレクション フレームワークの優先キューの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。