1. Prioritätsqueue -Datenstruktur
Die Datenstruktur von Prioritätsqueue (Prioritätswarteschlange) in JDK7 ist ein binärer Haufen. Um genau zu sein, ist es ein kleinster Haufen.
Ein binärer Haufen ist ein spezieller Haufen, der ungefähr ein vollständiger binärer Baum ist. Der binäre Heap erfüllt die Eigenschaften: Der Schlüsselwert des übergeordneten Knotens hält immer eine Beziehung mit fester Ordnung mit dem Schlüsselwert eines beliebigen untergeordneten Knotens bei, und der linke Teilbaum und der rechte Subtree jedes Knotens sind ein binärer Haufen.
Der maximale Heap ist, wenn der Schlüsselwert des übergeordneten Knotens immer größer oder gleich dem Schlüsselwert eines untergeordneten Knotens ist. Der minimale Heap ist, wenn der Schlüsselwert des übergeordneten Knotens immer geringer oder gleich dem Schlüsselwert eines untergeordneten Knotens ist.
Die folgende Abbildung ist ein maximaler Haufen
PriorityQueue -Teamheader ist das kleinste Element in der angegebenen Reihenfolge.
PriorityQueueue erlaubt keine Nullwerte und unterstützt nicht vergleichbare Objekte. Priorityqueue erfordert die Verwendung vergleichbarer und vergleichender Schnittstellen, um Objekte zu sortieren, und die darin enthaltenen Elemente werden nach Priorität beim Sortieren verarbeitet.
Die Größe der Priorität ist unbegrenzt, aber die anfängliche Größe kann beim Erstellen angegeben werden. Beim Hinzufügen von Warteschlangenelementen wird die Warteschlange automatisch erweitert.
PriorityQueueue ist nicht mit Gewinde, ähnlich Prioritätsblocking ist fadensicher.
Wir wissen, dass Warteschlangen den ersten im ersten Out-Modus folgen, aber manchmal müssen Objekte auf der Grundlage der Priorität in der Warteschlange verarbeitet werden. Zum Beispiel haben wir eine Anwendung, die während der täglichen Handelszeiten Aktienberichte generiert, für die viele Daten verarbeitet werden müssen und viel Verarbeitungszeit benötigt. Wenn der Client eine Anfrage an diese Anwendung sendet, tritt er tatsächlich in die Warteschlange ein. Wir müssen uns zuerst mit vorrangigen Kunden und dann mit normalen Benutzern befassen. In diesem Fall ist Javas Priorität (vorrangige Warteschlange) sehr hilfreich.
PriorityQueue ist eine unbegrenzte Warteschlange, die auf dem Prioritätshaufen basiert. Die Elemente in dieser Prioritätswarteschlange können standardmäßig auf natürliche Weise sortiert oder sortiert werden, wenn die Warteschlange durch den bereitgestellten Komparator instanziiert wird.
Priority-Warteschlangen erlauben keine Nullwerte und unterstützen nicht vergleichbare Objekte, wie z. B. benutzerdefinierte Klassen. Die vorrangige Warteschlange erfordert die Verwendung von Java vergleichbar und vergleichende Schnittstellen zur Sortierung von Objekten, und die darin enthaltenen Elemente werden bei der Sortierung gemäß Priorität verarbeitet.
Der Header der Prioritätswarteschlange ist das kleinste Element, das auf natürlicher Sortierung oder Vergleichssortierung basiert. Wenn mehrere Objekte die gleiche Sortierung haben, ist es möglich, zufällig eines davon zu nehmen. Wenn wir die Warteschlange bekommen, geben wir das Header -Objekt der Warteschlange zurück.
Die Größe der Prioritätswarteschlange ist uneingeschränkt, aber die anfängliche Größe kann zum Erstellungszeitpunkt angegeben werden. Wenn wir der vorrangigen Warteschlange Elemente hinzufügen, erhöht sich die Warteschlangengröße automatisch.
PriorityQueue ist nicht-thread-safe, daher bietet Java PriorityBlockingQueue (implementiert die Blockingqueue-Schnittstelle) für Java-Multi-Thread-Umgebungen.
2. Prioritätsquellcodeanalyse
Mitglied:
Priavte Transient Object [] Warteschlange; private int size = 0;
1. Der Prozess des Erstellens eines kleinen oberen Haufens durch Prioritätsqueue
Hier verwenden wir den PriorityQueueus -Konstruktor, um in einem Container als Parameter -Prioritätsqueue zu passieren (Collecntion <? Erweitert E> Beispiel:
Der Prozess des Konstruktion eines kleinen oberen Haufens ist grob in zwei Schritte unterteilt:
Kopieren Sie die Containerdaten und überprüfen Sie, ob die Containerdaten null sind
private void Initelements aus der Abnahme (Sammlung <? Erweitert E> c) {Object [] a = c.toarray (); // Wenn C.Toarray falsch kein Objekt [] zurückgibt, kopieren Sie es. if (a.getClass ()! = Object []. Klasse) a = arrays.copyof (a, A.Length, Objekt []. Klasse); int len = a.länge; if (len == 1 || this.comParator! this.queue = a; this.size = A.Length;} Passen Sie an, um die Daten die Struktur des kleinen oberen Haufens zu erfüllen.
Erstens zwei Anpassungsmethoden: Siftup und Siftdown
SIFTDOWN: Wenn ein Initialisierungselement angegeben wird, sollte das Element so angepasst werden, dass es den strukturellen Eigenschaften des Mindesthaufens erfüllt. Daher wird der Schlüsselwert des Elements x ständig verglichen und mit dem Kind von oben nach unten ausgetauscht, bis festgestellt wird, dass der Schlüsselwert von Element X kleiner oder gleich dem Schlüsselwert des Kindes ist (dh garantiert kleiner als die linken und rechten Knotenwerte), oder er fällt in den Blattknoten.
Passen Sie diesen Knoten 9 beispielsweise, wie im folgenden Diagramm gezeigt:
Private void Siftdown Comparable (int k, e x) {vergleichbar <? super e> key = (vergleichbar <? Super e>) x; int halb = Größe >>> 1; // Größe/2 ist das Index des ersten Blattknotens //, solange der Blattknoten nicht erreicht ist, während (k <halb) {int child = (k << 1) + 1; // links untergeordnetes Objekt c = Warteschlange [Kind]; int rechts = Kind + 1; // Die kleinsten und kleinsten Kinder der linken und rechten Kinder finden (rechts <Größe && ((vergleichbar <? Super E>) c) .Compareto ((e) Warteschlange [rechts])> 0) c = Queue [Child = rechts]; if (key.comPareto ((e) c) <= 0) brechen; Warteschlange [k] = C; k = Kind; } Warteschlange [k] = key;} SIFTUP: PriorityQueue fügt das neue Element jedes Mal in den Schwanz ein, wenn ein neues Element hinzugefügt wird. Daher sollte der gleiche Einstellungsprozess wie SIFTDOWN vorhanden sein, außer dass es von unten (Blatt) nach oben eingestellt wird.
Füllen Sie beispielsweise den Knoten mit Key 3 im folgenden Diagramm aus:
private void SIFTUPCARABLE (int k, e x) {vergleichbar <? super e> key = (vergleichbar <? Super e>) x; while (k> 0) {int parent = (k - 1) >>> 1; // übergeordnetes Einweisobjekt e = Queue [übergeordnet] erhalten; if (key.comPareto ((e) e)> = 0) brechen; Warteschlange [k] = e; K = Eltern; } Warteschlange [k] = key;}Der Gesamtprozess des Aufbaus eines kleinen oberen Haufens ist:
private void initfromCollection (Sammlung <? Erweitert E> c) {initelements fromCollection (c); schwer(); }Unter ihnen ist Heapify der Prozess des Siftdowns.
2. PriorityQueue -Kapazitätserweiterungsprozess
Wie aus den Instanzmitgliedern hervorgeht, verwaltet PriorityQueueue ein Objekt [], sodass seine Expansionsmethode der Bestellentabellen -ArrayList ähnelt.
Hier wird nur der Quellcode der Wachstummethode angegeben
private void wachsen (int mincapacity) {int oldcapacity = queue.length; // doppelte Größe, wenn klein; sonst wachsen um 50% int NewCapacity = OldCapacity + ((OldCapacity <64)? (OldCapacity + 2): (OldCapacity >> 1)); // überlaufbewusster Code if (NewCapacity - max_array_size> 0) newcapacity = Hugenkapazität (mincapacity); queue = arrays.copyof (Warteschlange, NewCapacity); }Es ist ersichtlich, dass die Kapazität nicht jedes Mal groß ist, wenn die Kapazität des Arrays nicht groß ist. Wenn die Array -Kapazität größer als 64 ist, wird jedes Mal das Doppel erweitert.
3. Prioritätsqueue -Anwendung
EG1:
Hier ist die einfachste Anwendung: Finden Sie die K-D-größte Zahl aus dynamischen Daten.
Die Idee ist, einen kleinen oberen Stapel mit Größe = K aufrechtzuerhalten.
// Daten sind dynamische Daten // Heap verwaltet dynamische Daten // res wird verwendet, um den K-Most Value Public Boolean Kthlargest (int Data, int k, priorityQueue <GanzEger> heap, int [] res) {if (heap.size () <k) {Heap.fer (Data)) zu speichern. if (heap.size () == k) {res [0] = heap.peek (); zurückkehren; } return false; } if (heap.peek () <data) {heap.poll (); heap.offer (Daten); } res [0] = heap.peek (); zurückkehren; }
EG2:
Wir haben einen Kundenklassenkunde, der keine Art von Sorte bereitstellt. Wenn wir es verwenden, um eine Prioritätswarteschlange zu erstellen, sollten wir es mit einem Komparatorobjekt zur Verfügung stellen.
Customer.java
Paket com.journaldev.collections; öffentliche Klasse Kunde {private int id; privater Zeichenfolge Name; public customer (int i, string n) {this.id = i; this.name = n; } public int getid () {return id; } public String getName () {return name; }} Wir verwenden Java -Zufallsnummern, um zufällige Benutzerobjekte zu generieren. Für die natürliche Sortierung verwenden wir Integer -Objekte, das auch ein eingekapseltes Java -Objekt ist.
Hier ist der endgültige Testcode, der zeigt, wie Prioritätsqueue verwendet wird:
PriorityQueueExample.java
Paket com.journaldev.collections; Import Java.util.comParator; Import Java.util.Priorityqueue; Import Java.util.queue; Import Java.util.random; PriorityQueueExample public class {public static void main (String [] args) {// Priority Queue natürliche Sortierung Beispiel Queue <Grapier> IntegerPriorityQueue = New PriorityQueue <> (7); Random rand = new random (); für (int i = 0; i <7; i ++) {IntegerPriorityQueue.add (New Integer (Rand.Nextint (100))); } für (int i = 0; i <7; i ++) {Integer in = IntegerPriorityQueue.poll (); System.out.println ("Verarbeitung Integer:"+in); } // Priority Queue -Nutzungsnutzung Beispiel Warteschlange <Custices> CustomerPriorityQueue = New PriorityQueue <> (7, idComparator); AddDatatoqueue (CustomerPriorityQueue); polldatafromQueue (CustomerPriorityQueue); } // Anonymous Comparator implementiert public static vergleicher <custic> idComparator = neuer Vergleicher <custic> () {@Override public int compare (customer c1, customer c2) {return (int) (c1.getid () - c2getid ()); }}; // Universelle Methode zum Hinzufügen von Daten zur Queue private statische void addDatatoqueue (Warteschlange <Custic> CustomerPriorityQueue) {Random Rand = new random (); für (int i = 0; i <7; i ++) {int id = rand.nextint (100); CustomerPriorityQueue.add (neuer Kunde (ID, "Pankaj"+ID)); }} // Allgemeine Methode zum Abholen von Daten aus einer Warteschlange private statische void polldatafromQueue (Queue <Custic> customerPriorityQueue) {while (true) {customer Cust = customerPriorityQueue.poll (); if (Cust == null) brechen; System.out.println ("Kunde bearbeiten mit id ="+cust.getId ()); }}}} Beachten Sie, dass ich Java Anonymous Class verwende, die die Komparatorschnittstelle implementiert und einen ID-basierten Komparator implementiert.
Wenn ich das obige Testprogramm ausführe, erhalte ich die folgende Ausgabe:
Processing Integer:9Processing Integer:16Processing Integer:18Processing Integer:25Processing Integer:33Processing Integer:75Processing Integer:77Processing Customer with ID=6Processing Customer with ID=20Processing Customer with ID=24Processing Customer with ID=28Processing Customer with ID=29Processing Customer with ID = 82 Verarbeitung des Kunden mit ID = 96
Aus den Ausgangsergebnissen ist deutlich zu erkennen, dass das kleinste Element dann zuerst am Kopf der Warteschlange herausgenommen wird. Wenn der Komparator nicht implementiert wird, wird eine ClassCastException beim Erstellen eines Kundenprioritätsqueue geworfen.
Ausnahme in Thread "Haupt" java.lang.classcastexception: com.journaldev.collections.Customer kann nicht an java.lang.comparable unter java.util.priorityQueue.SiftupComparable (PrioritätsQueue.java: 629) bei java.util.priority (prioritysQueue.java: 629) bei java.util.priorität (prioritHequeue (priorityqueue) gegossen werden. java.util.priorityqueue.offer (priorityQueue.java:329) unter java.util.priorityqueue.add (PriorityQueue.java:306) unter com.journaldev.collections.Priorityqueuexample.addatatoqueue (priorityQueuexampion.java:45) bei com.journaldev.collections.PriorityQueueExample.main (PriorityQueueExample.java:25)