Dies ist direkt aus dem Java Dokumente :
Diese Klasse und ihr Iterator implementieren alle optionalen Methoden der Collection- und Iterator-Schnittstellen. Der in method iterator () bereitgestellte Iterator garantiert nicht unbedingt die Elemente der Prioritätswarteschlange in einer bestimmten Reihenfolge. Wenn Sie eine geordnete Traversierung benötigen, sollten Sie die Verwendung von Arrays.sort (pq.toArray ()) in Erwägung ziehen.
Im Prinzip funktioniert meine PriorityQueue gut, aber das Drucken auf dem Bildschirm mit der eigenen eingebauten toString () -Methode hat mich dazu gebracht, diese Anomalie in Aktion zu sehen und mich gefragt, ob jemand erklären könnte, warum der Iterator bereitgestellt wurde (und intern verwendet) durchläuft die PriorityQueue nicht in ihrer natürlichen Reihenfolge?
Weil die zugrunde liegende Datenstruktur dies nicht unterstützt. Ein binärer Heap ist nur teilweise geordnet, mit dem kleinsten Element am Stamm. Wenn Sie das entfernen, wird der Heap neu angeordnet, sodass sich das nächstkleinere Element im Stammverzeichnis befindet. Es gibt keinen effizient geordneten Traversalalgorithmus, so dass in Java keiner bereitgestellt wird.
Bei der ersten Schätzung werden die Daten wahrscheinlich in der Reihenfolge durchlaufen, in der sie gespeichert sind. Um die Zeit für das Einfügen eines Elements in die Warteschlange zu minimieren, werden normalerweise nicht alle Elemente in sortierter Reihenfolge gespeichert.
PriorityQueues werden mithilfe von binärer Heap implementiert. Ein Heap ist keine sortierte Struktur und ist teilweise geordnet. Jedem Element ist eine "Priorität" zugeordnet. Mit einem Heap zum Implementieren einer Prioritätswarteschlange wird immer das Element mit der höchsten Priorität im Stammknoten des Heapspeichers enthalten sein. In einer Prioritätswarteschlange wird also ein Element mit hoher Priorität vor einem Element mit niedriger Priorität bereitgestellt. Wenn zwei Elemente die gleiche Priorität haben, werden sie entsprechend ihrer Reihenfolge in der Warteschlange bedient. Heap wird nach jedem Entfernen von Elementen aktualisiert, um die Heap-Eigenschaft
beizubehaltenNun, wie der Javadoc sagt, ist es so implementiert worden. Die Prioritätswarteschlange verwendet wahrscheinlich einen binären Heap als zugrunde liegende Datenstruktur. Wenn Sie Elemente entfernen, wird der Heap neu angeordnet, um die Heap-Eigenschaft beizubehalten.
Zweitens ist es unklug, eine bestimmte Implementierung anzubinden (erzwingt eine sortierte Reihenfolge). Mit der aktuellen Implementierung können Sie sie in beliebiger Reihenfolge durchlaufen und jede Implementierung verwenden.
Binary Heaps sind eine effiziente Möglichkeit, Prioritätswarteschlangen zu implementieren. Die einzige Garantie für die Reihenfolge, die ein Heap ausführt, ist, dass der oberste Punkt die höchste Priorität hat (vielleicht ist er der "Größte" oder "Kleinste" nach einer bestimmten Reihenfolge). Ein Heap ist ein Binärbaum mit den folgenden Eigenschaften: Shape-Eigenschaft: Der Baum füllt sich von oben nach unten von links nach rechts Reihenfolge: Das Element an jedem Knoten ist größer (oder kleiner, wenn der kleinste die höchste Priorität hat) als seine zwei untergeordneten Knoten. Wenn der Iterator alle Elemente besucht, tut er dies wahrscheinlich in einer Ebene-Reihenfolge-Durchquerung, d. H. Er besucht jeden Knoten in jeder Ebene der Reihe nach, bevor er zur nächsten Ebene übergeht. Da die einzige Garantie für die Reihenfolge, dass ein Knoten eine höhere Priorität als seine Kinder hat, sind die Knoten in jeder Ebene in keiner bestimmten Reihenfolge.
Tags und Links java priority-queue