Warum füllt die Prioritätswarteschlange in Java mit Offer() sie in alphabetischer Reihenfolge auf, während sie auch großgeschriebenen Wörtern Priorität einräumt?

Question

Ich bin verwirrt. Offer() füllt die Liste in alphabetischer Reihenfolge auf und auch hier werden Großwörter bevorzugt. Wie fülle ich die Liste in der Reihenfolge, in der ich sie eintippe?

import java.util.*; 
public class Bucky { 

public static void main(String[] args) { 
    PriorityQueue<String> q= new PriorityQueue<String>(); 
    q.offer("first"); 
    q.offer("aecond"); 
    q.offer("zhird"); 

    System.out.printf("%s ",q); 
    System.out.println(); 
    System.out.printf("%s ", q.peek()); 
    System.out.println(); 


} 

} 

o/p = [aecond, zuerst, zhird] aecond

---

import java.util.*; 
public class Bucky { 

public static void main(String[] args) { 
    PriorityQueue<String> q= new PriorityQueue<String>(); 
    q.offer("first"); 
    q.offer("aecond"); 
    q.offer("Zhird"); 

    System.out.printf("%s ",q); 
    System.out.println(); 
    System.out.printf("%s ", q.peek()); 
    System.out.println(); 


} 

} 

o/p = [Zhird, zuerst, aecond] Zhird

Answer 1

Ich denke, was Sie in Frage stellen, ist die Reihenfolge der Elemente im Array. Das heißt, wenn Sie die Zeile System.out.printf("%s ",q); ausführen, erhalten Sie die Ausgabe [Zhird, first, aecond], und Sie fragen sich, warum das zweite Element im Array first ist, wenn es lexikographisch größer als aecond ist.

Die Antwort liegt in der Struktur der Prioritätswarteschlange. Es ist als binary heap strukturiert und unterliegt der Art, wie ein binärer Heap konstruiert wird.

Ihr Code erstellt den Haufen wie folgt aus:

q.offer("first"); 
q.offer("aecond"); 
q.offer("Zhird"); 

Wenn wir von der Halde als Baum denken, können Sie leichter sehen, was passiert. Der erste Aufruf platziert "first" an der Wurzel des Baums. Die Regeln zum Erstellen eines binären Heapspeichers sagen, dass beim nächsten Aufruf die Zeichenfolge "aecond" an der untersten Stelle ganz links platziert wird und dann die Struktur neu angeordnet wird. Also zuerst haben Sie:

 "first" 
    /
    "aecond" 

Dann arbeiten Sie sich den Baum hinauf. Wenn das Kind kleiner ist als das Elternteil, dann tauschen Sie Eltern und Kind aus. Also in diesem Fall am Ende mit dem Baum:

 "aecond" 
    /
    "first" 

Nun wird die Zeichenfolge "Zhird" kommt. Es wird hinzugefügt, um die niedrigsten, am weitesten links stehenden Position, die nicht belegten ist:

 "aecond" 
    /  \ 
    "first" "Zhird" 

Und es ist Zeit, wieder den Baum neu zu ordnen. "Zhird" lexikographisch kleiner als "aecond", so dass sie ausgetauscht:

 "Zhird" 
    /  \ 
    "first" "aecond" 

Beachten Sie, dass dies immer noch ein gültiger Heap ist. Die untergeordneten Knoten sind größer als das übergeordnete Element.

Die Array-Repräsentation des binären Heaps ist im Grunde nur eine Breite-zuerst-Traversierung des Baums, daher wird dieser Baum als ["Zhird", "first", "aecond"] dargestellt.

Wenn Sie Elemente einzeln aus dem Heap entfernen, erhalten Sie sie in der richtigen Reihenfolge (d. H. "Zhird", "aecond", "first"). Die Array-Repräsentation kann sich jedoch stark von der strikt lexikographischen Reihenfolge unterscheiden, da der Entfernungsprozess den Baum neu anordnet. Wenn Sie das erste Element aus der Warteschlange entfernen würden (z., rufen Sie q.poll), und geben Sie dann das Array aus, Sie würden sehen, dass es zu ["aecond", "first"] umgeordnet wurde.

In meinem Blog, http://blog.mischel.com/2013/09/29/a-better-way-to-do-it-the-heap/, finden Sie eine Erklärung der Heap-Einfüge- und -Entfernungsregeln. Lesen Sie den Folgeartikel http://blog.mischel.com/2013/09/30/a-simple-heap-of-integers/ für eine Implementierung, die Ihnen helfen soll zu verstehen, wie der Baum einem Array zugeordnet ist.

Auch, wenn Sie den Heap in dieser Reihenfolge zu füllen sind:

q.offer("Zhird"); 
q.offer("first"); 
q.offer("aecond"); 

Der Ausgang wäre [Zhird, first, aecond]. Aber wenn Ihre Bestellung war:

Die Ausgabe wäre [Zhird, aecond, first].

Answer 2

Wenn Sie wollen den Fall ignorieren, es ist ein einfaches wie:

new PriorityQueue<>(String.CASE_INSENSITIVE_ORDER);