PriorityQueue-Prioritätswarteschlange des Java-Sammlungsframeworks

Dieser Artikel vermittelt Ihnen relevantes Wissen über Java, das hauptsächlich das relevante Wissen über PriorityQueue-Prioritätswarteschlangen vorstellt. Das Java-Sammlungsframework bietet zwei Arten von Prioritätswarteschlangen: PriorityQueue und PriorityBlockingQueue ist ein Thread. PriorityBlockingQueue ist ein Thread -sicher. Schauen wir es uns an. Ich hoffe, es wird für alle hilfreich sein.

Empfohlene Studie: „Java-Video-Tutorial“

Das Java-Sammlungsframework bietet zwei Arten von Prioritätswarteschlangen: PriorityQueue und PriorityBlockingQueue. PriorityQueue ist threadsicher und PriorityBlockingQueue ist hauptsächlich threadsicher führt PriorityQueue ein

Die Beziehung von PriorityQueue im Java Collection Framework ist wie folgt:

1. Hinweise zur Verwendung von PriorityQueue

1. Wenn Sie es verwenden, müssen Sie das Paket importieren, in dem sich PriorityQueue befindet, das heißt:

import java.PriorityQueue

2. Die in der PriorityQueue platzierten Elemente können nicht eingefügt werden, da sonst eine
ClassCastException ausgelöst wird 3. Ein Nullobjekt kann nicht eingefügt werden, da es sonst eine NullPointerException auslöst. Es gibt keine Kapazitätsbeschränkung, und die interne Kapazität kann automatisch erweitert werden Das Einfügen und Löschen von Elementen ist log n mit Basis 2

6. Die zugrunde liegende Verwendung von PriorityQueue ist standardmäßig ein kleiner Heap – das heißt, die jedes Mal erhaltenen Elemente sind die kleinsten Elemente (

Wenn wir einen großen Heap erstellen möchten, müssen wir die Methode erneut vergleichen. Die Standardvergleichsmethode ist die CompareTo-Methode in der Comparable-Schnittstelle)

2. Einführung in gängige Schnittstellen von PriorityQueue

1. Konstruktion der Priorität queue

Hier sind nur einige gängige Konstruktionsmethoden in

PriorityQueue, Sie können auf das Hilfedokument für andere verweisen.

Konstruktor

Funktionseinführung

PriorityQueue()Erstellen Sie eine leere Prioritätswarteschlange. PriorityQueue(intHinweis: initialCapacity darf nicht kleiner als 1 sein, sonst wird eine IllegalArgumentException ausgelöst PriorityQueue(Comparator<? super E> comparator)Erstellt eine Prioritätswarteschlange Standardanfangskapazität und bewertet ihre Elemente basierend auf dem spezifizierten Komparator Vergleichen

Die Standardkapazität beträgt 11
initialCapacity)	Erstellen Sie eine anfängliche A-Priorität Warteschlange mit einer Kapazität von initialCapacity,
Oft	PriorityQueue(Collection erweitert E> c)Verwenden Sie eine Sammlung zum Erstellen eine Prioritätswarteschlange
	mit
PriorityQueue(Comparator<? super E> comparator)	创建具有默认初始容量的优先级队列，并根据指定的比较器对其元素进行比较
PriorityQueue(int initialCapacity, Comparator <? super E> comparator)	创建一个初始容量为<strong>initialCapacity</strong>的优先级队列PriorityQueue(int initialCapacity, Comparator <? super E> comparator) Erstellen Sie eine Prioritätswarteschlange mit der Anfangskapazität von <strong>initialCapacity</strong> , vergleichen Sie seine Elemente gemäß dem von

angegebenen Komparator 🎜Hinweis: 🎜🎜initialCapacity darf nicht kleiner als 1 sein, andernfalls wird 🎜normalerweise🎜🎜🎜🎜🎜 eine IllegalArgumentException ausgelöst

2. Vergleich der Elemente in der PriorityQueue

Nachdem wir die Konstruktionsmethode gelesen haben, denken wir noch einmal über eine Frage nach

Wie erreicht die Prioritätswarteschlange die Reihenfolge? Da die Prioritätswarteschlange mit Hilfe des kleinen Root-Heaps implementiert wird

Während des Implementierungsprozesses des kleinen Root-Heaps wissen wir, dass ein Vergleich der Elemente erfolgen muss, sodass die Elemente in der PriorityQueue in der Größe vergleichbar sein müssen Wie führt PriorityQueue den Elementvergleich durch?

PriorityQueue verwendet zwei Methoden:
Comparble und Comparator.

1. Comparble ist die standardmäßige interne Vergleichsmethode Wenn der Benutzer ein benutzerdefiniertes Objekt einfügt, muss das Objekt die Comparble-Schnittstelle implementieren und die CompareTo-Methode

2 überschreiben Objekt: Wenn der Benutzer ein benutzerdefiniertes Typobjekt einfügt, muss er eine Komparatorklasse bereitstellen, die Klasse die Komparatorschnittstelle implementieren lassen und die Vergleichsmethode überschreiben.

Wir sehen, dass das Programm hier einen Fehler gemeldet hat, warum? Da das von uns eingefügte untergeordnete Objekt nicht vergleichbar ist (

das heißt, es implementiert nicht die Comparable-Schnittstelle und verwendet keinen benutzerdefinierten Komparator)

Sie können sehen

Das heißt, wir verwenden die Standardvergleichsmethode in der Comparable-Schnittstelle „compareTo“-Methode

Zu diesem Zeitpunkt schauen wir uns die Fehlermeldung noch einmal an

Es scheint, dass beim Einfügen von Elementen in die PriorityQueue ein Problem vorliegt

Dann öffnen wir die Quellcode von PriorityQueue und werfen Sie einen Blick darauf (

unten) Es ist der Quellcode der Angebotsmethode in PriorityQueue)

Schauen Sie sich noch einmal den Quellcode von ShiftUp an

Klicken Sie weiter auf siftUpComparable

Lassen Sie uns zu diesem Zeitpunkt zurückgehen und einen Blick auf das untergeordnete Objekt werfen, das wir in PriorityQueue eingefügt haben.

Es verfügt weder über einen benutzerdefinierten Komparator noch implementiert es die Comparable-Schnittstelle. Natürlich meldet es einen Fehler!

Okay, dann implementieren wir die Comparable-Schnittstelle in der Child-Klasse und vergleichen sie nach Alter , dann wenn Wie wäre es, wenn wir einen Altersvergleich anpassen?

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);
    }
}

3. Element mit der höchsten Priorität einfügen/löschen/holen e, erfolgreich einfügen Rückkehr wahr. Wenn das e-Objekt leer ist, wird eine NullPointerException ausgelöst. Die Zeitkomplexität beträgt

E peek()

Priorität. Wenn die Prioritätswarteschlange leer ist, geben Sie null zurück Anzahl gültiger Elemente

Levoidar Clear ()

Clear

Boolean Isemty () Erkennen, ob die Prioritätswarteschlange leer ist, um True zurückzugeben》

Empfohlenes Lernen: „ Java-Video-Tutorial

Das obige ist der detaillierte Inhalt vonPriorityQueue-Prioritätswarteschlange des Java-Sammlungsframeworks. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!