Der eingebaute Iterator für die PriorityQueue von Java durchläuft die Datenstruktur nicht in einer bestimmten Reihenfolge. Warum?

Lesezeit: 3 Minuten

Das kommt direkt von der Java-Dokumente:

Diese Klasse und ihr Iterator implementieren alle optionalen Methoden der Schnittstellen Collection und Iterator. Es ist nicht garantiert, dass der in der Methode iterator() bereitgestellte Iterator die Elemente der Prioritätswarteschlange in einer bestimmten Reihenfolge durchläuft. Wenn Sie eine geordnete Traversierung benötigen, ziehen Sie die Verwendung von Arrays.sort(pq.toArray()) in Betracht.

Meine PriorityQueue funktioniert also im Grunde gut, aber das Ausdrucken auf dem Bildschirm mit der eigenen integrierten toString() -Methode hat dazu geführt, dass ich diese Anomalie in Aktion gesehen habe, und ich habe mich gefragt, ob jemand erklären könnte, warum der Iterator bereitgestellt (und verwendet) wurde intern) durchläuft die PriorityQueue nicht in ihrer natürlichen Reihenfolge?

Weil die zugrunde liegende Datenstruktur dies nicht unterstützt. Ein binärer Haufen ist nur teilweise geordnet, mit dem kleinsten Element an der Wurzel. Wenn Sie das entfernen, wird der Heap neu geordnet, sodass sich das nächstkleinere Element an der Wurzel befindet. Es gibt keinen effizienten geordneten Traversalalgorithmus, daher wird in Java keiner bereitgestellt.

PriorityQueues werden mit implementiert binärer Haufen.
Ein Heap ist keine sortierte Struktur und teilweise geordnet. Jedem Element ist eine „Priorität“ zugeordnet. Wenn ein Heap verwendet wird, um eine Prioritätswarteschlange zu implementieren, wird es immer das Element mit der höchsten Priorität im Wurzelknoten des Heaps haben. In einer Prioritätswarteschlange wird also ein Element mit hoher Priorität vor einem Element mit niedriger Priorität bedient. Wenn zwei Elemente die gleiche Priorität haben, werden sie gemäß ihrer Reihenfolge in der Warteschlange bedient. Heap wird nach jedem Entfernen von Elementen aktualisiert, um die Heap-Eigenschaft beizubehalten

Auf den ersten Blick werden die Daten wahrscheinlich in der Reihenfolge durchlaufen, in der sie gespeichert sind. Um die Zeit zum Einfügen eines Elements in die Warteschlange zu minimieren, werden normalerweise nicht alle Elemente in sortierter Reihenfolge gespeichert.

Nun, wie das Javadoc sagt, wurde es so implementiert. Die Prioritätswarteschlange verwendet wahrscheinlich einen binären Heap als zugrunde liegende Datenstruktur. Wenn Sie Elemente entfernen, wird der Heap neu geordnet, um die Heap-Eigenschaft beizubehalten.

Zweitens ist es unklug, eine bestimmte Implementierung einzubinden (eine sortierte Reihenfolge zu erzwingen). Mit der aktuellen Implementierung können Sie sie in beliebiger Reihenfolge durchlaufen und jede Implementierung verwenden.

Binäre Heaps sind eine effiziente Möglichkeit, Prioritätswarteschlangen zu implementieren. Die einzige Garantie für die Ordnung, die ein Haufen macht, ist, dass das oberste Element die höchste Priorität hat (vielleicht ist es je nach Reihenfolge das “größte” oder “kleinste”). Ein Heap ist ein binärer Baum mit den folgenden Eigenschaften: Formeigenschaft: Der Baum füllt sich von oben nach unten von links nach rechts Ordnungseigenschaft: Das Element an jedem Knoten ist größer (oder kleiner, wenn das kleinste die höchste Priorität hat) als seine beiden untergeordneten Knoten. Wenn der Iterator alle Elemente besucht, tut er dies wahrscheinlich in einer Ebenenreihenfolge, dh er besucht nacheinander jeden Knoten in jeder Ebene, bevor er zur nächsten Ebene übergeht. Da die einzige Garantie für die Reihenfolge, die gemacht wird, dass ein Knoten eine höhere Priorität als seine Kinder hat, werden die Knoten in jeder Ebene in keiner bestimmten Reihenfolge sein.

  • Das ist nicht ganz richtig. Der Heap hat auch die Garantie, dass x[i] <= x[2i] <= x[2i+1].

    – Benutzer207421

    25. Januar 2011 um 0:18 Uhr

  • Das ist nicht ganz richtig. Der Heap hat auch die Garantie, dass x[i] <= x[2i] <= x[2i+1].

    – Benutzer207421

    25. Januar 2011 um 0:18 Uhr

1001830cookie-checkDer eingebaute Iterator für die PriorityQueue von Java durchläuft die Datenstruktur nicht in einer bestimmten Reihenfolge. Warum?

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy