Reihenfolge der PrioritätQueue in Java?

Question

Ich kann die Reihenfolge von PriorityQueue in Java nicht verstehen. Wie ich verstehe, sind sie heap-basiert und sie können keine exakte Iterationsreihenfolge als Einfügereihenfolge liefern. Ich möchte dann wissen auf welcher Basis priorityQueue sich selbst sortieren. Gegeben Code:

PriorityQueue<String> pq = new PriorityQueue<String>(); 
     pq.offer("hepqo"); 
     pq.offer("bro"); 
     pq.offer("wassup"); 
     pq.offer("okay"); 
     pq.offer("bingo"); 
     pq.offer("first"); 
     pq.offer("last"); 
     pq.offer("ssup"); 
     System.out.println("polled "+pq.poll()); 
     System.out.println(pq); 
     String str[] = pq.toArray(new String[0]); 
     Arrays.sort(str); 
     for(String str1:str){ 
      System.out.println(str1); 
     } 

erzeugt eine Ausgabe:

polledbingo 
[bro, hepqo, first, okay, ssup, wassup, last] 
bro 
first 
hepqo 
last 
okay 
ssup 
wassup 

Selbst wenn ich es zu Array umwandeln, die Ordnung verloren.
Ich kann nicht glauben, dass dies sogar NATURAL ORDERING von String ist.
Gibt es eine Möglichkeit, die Reihenfolge der Prioritätswarteschlangen beizubehalten?
Auf welcher Grundlage haben sie sortiert?

Answer 1

Die Warteschlange sortiert nach der lexikographischen Reihenfolge der Zeichenfolgen, was ihrer natürlichen Reihenfolge entspricht (d. H. "B" geht vor "f", "f" geht vor "h" usw.). Wenn Sie die Warteschlange halten Auftrag mögen, verwenden Sie dann eine Vanille Queue anstelle eine PriorityQueue

Answer 2

Die Prioritäts-Warteschlangen in Java ist eine Implementierung der sogenannten ein Heap (das ist eine abstrakte Datenstruktur). Wenn Sie die Heap-Datenstruktur betrachten, gibt es kein striktes Prinzip der Anordnung unter den Schlüsseln (oder den Auflistungselementen in Java-Begriffen). Heap ADT eignet sich hauptsächlich für schnelles Einfügen/Löschen und O (K) -Zeitabruf des ersten Elements (welches die Wurzel im Falle des Heaps sein wird). Verwenden Sie daher die Datenstruktur "PriorityQueue" in Java nicht zum Suchen aller Elemente, zum Sortieren von Elementen oder zum Versetzen von Elementen. Weil es nicht für diese Zwecke gedacht ist. Das Javadoc weist klar darauf hin, dass die optionalen Implementierungen von Collection und Iterable Interfaces nicht etwas sind, auf das man sich verlassen kann (dh Iterator gibt eine Implementierung zurück, die die Reihenfolge nicht garantiert und die Collection-Methoden remove(), contains() nehmen lineare Zeit)