この記事では、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 の関係は次のとおりです。
2.import java.util.PriorityQueue
PriorityQueue に配置された要素はサイズを比較できる必要があり、比較できないオブジェクトは比較できません。挿入できない場合、 ClassCastException## がスローされます。
#3. Null オブジェクトは挿入できません。そうでない場合は、NullPointerException がスローされます。
4. 容量制限はありません。 、任意の数の要素を挿入でき、内部容量は自動的に拡張できます
5 。要素の挿入と削除の
時間計算量は、対数 2 を底とします n6. PriorityQueue の最下層はヒープ データ構造を使用します
7. デフォルトの PriorityQueue は小さなヒープです ---つまり、毎回取得される要素は最小の要素です (
必要な場合大きなヒープにするには、メソッドを再比較する必要があります。デフォルトの比較メソッドは、Comparable インターフェイスの CompareTo メソッドです)2. PriorityQueue の共通インターフェイスの概要
の一般的な構築方法をいくつか紹介しますが、その他についてはヘルプ ドキュメントを参照してください。
関数の紹介 | ||||||||||||||
空の優先キューを作成する, | デフォルトの容量は 11||||||||||||||
#を作成します。 | 初期容量は、initialCapacity優先キュー、注: initialCapacity を 1 より小さくすることはできません。それ以外の場合は、IllegalArgumentException がスローされます。 Often | |||||||||||||
コレクションを使用して優先キューを作成します | ||||||||||||||
デフォルトの初期容量で優先キュー を作成し、その要素 |
を 指定されたコンパレータ # と比較します。 | ##PriorityQueue(int initialCapacity, Comparator super E> comparator)|||||||||||||
初期容量は#initialCapacity#を作成します## の優先キュー | #、指定されたコンパレータ
2. PriorityQueue の要素の比較構築方法を読んだ後、もう一度質問を考えてみましょう プライオリティ キューはどのようにして順序を達成するのでしょうか?プライオリティ キューは小さなルート ヒープを利用して実装されるため、 #小さなルート ヒープを実装するプロセスでは、要素の比較が必要であることがわかっているため、PriorityQueue 内の要素はでは、PriorityQueue はどのようにして要素を比較するのでしょうか?PriorityQueue は、 プログラムがここでエラーを報告していることがわかります。なぜでしょうか?挿入した 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); } } ログイン後にコピー
|
以上がPriorityQueue Java コレクション フレームワークの優先キューの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。