Beispielanalyse eines Heap-Sortieralgorithmus in Java

Dieser Artikel stellt hauptsächlich den relevanten Code des Java-Heap-Sortieralgorithmus im Detail vor. Er hat einen bestimmten Referenzwert.

Heap ist eine wichtige Art von Datenstruktur, die das Konzept versteht und der Betrieb von „Heap“ kann uns helfen, die Heap-Sortierung schnell zu meistern.

Das Konzept des Heaps

Ein Heap ist ein spezieller vollständiger Binärbaum. Wenn der Wert aller Knoten in einem vollständigen Binärbaum nicht kleiner ist als der seiner untergeordneten Knoten, wird er als Big-Root-Heap (oder Big-Top-Heap) bezeichnet. Wenn der Wert aller Knoten nicht größer ist als der seiner untergeordneten Knoten, wird er als Big-Root-Heap bezeichnet ein kleiner Root-Heap (oder kleiner Top-Heap).

Im Array (der Wurzelknoten ist bei Index 0 gespeichert) ist es einfach, die folgende Formel zu erhalten (diese beiden Formeln sind sehr wichtig):

1 Der Knoten mit Index i , die Koordinaten des übergeordneten Knotens sind (i-1)/2; Für den Knoten, dessen Index i ist, sind die Koordinaten des linken untergeordneten Knotens 2*i+1 und des rechten untergeordneten Knotens ist 2*i+2.

Erstellung und Wartung des Heaps

Der Heap kann eine Vielzahl von Vorgängen unterstützen, aber jetzt kümmern wir uns nur um zwei Probleme:

1. Wie kann man ein ungeordnetes Array als Heap erstellen?

2. Wie passt man das Array nach dem Löschen des obersten Elements des Heaps in einen neuen Heap an?

Schauen wir uns zunächst die zweite Frage an. Gehen wir davon aus, dass wir bereits einen großen Wurzelhaufen bereit haben. Jetzt haben wir das Stammelement gelöscht, aber keine anderen Elemente verschoben. Überlegen Sie, was passiert: Das Root-Element ist leer, aber die anderen Elemente behalten weiterhin die Heap-Eigenschaften. Wir können das letzte Element (Codename A) an die Position des Wurzelelements verschieben. Wenn es sich nicht um einen Sonderfall handelt, wird die Art des Heaps zerstört. Dies liegt jedoch nur daran, dass A kleiner ist als eines seiner Kinder. Daher können wir die Positionen von A und diesem Unterelement vertauschen. Wenn A größer als alle seine Unterelemente ist, wird der Heap angepasst. Andernfalls wird der obige Vorgang wiederholt und das A-Element „sinkt“ weiter in der Baumstruktur, bis die entsprechende Position erreicht ist und das Array seinen Heap zurückgewinnt Eigenschaften. Der obige Prozess wird im Allgemeinen als „Screening“ bezeichnet und die Richtung ist offensichtlich von oben nach unten.

Das Gleiche gilt für das Löschen eines Elements und das Gleiche gilt für das Einfügen eines neuen Elements. Der Unterschied besteht darin, dass wir das neue Element am Ende platzieren und es dann mit seinem übergeordneten Knoten vergleichen, also von unten nach oben filtern.

Wie löst man also das erste Problem?

Viele der Datenstrukturbücher, die ich gelesen habe, filtern vom ersten Nicht-Blattknoten nach unten, bis das Wurzelelement gefiltert wird. Diese Methode wird „Screening-Methode“ genannt und erfordert eine Schleife zum Screening von n/2 Elementen.

Wir können aber auch von der Idee „aus dem Nichts etwas machen“ lernen. Wir können das erste Element als Heap behandeln und ihm immer wieder neue Elemente hinzufügen. Diese Methode wird „Einfügemethode“ genannt und erfordert das Einfügen von (n-1) Elementen in eine Schleife.

Da die Filtermethode und die Einfügemethode unterschiedlich sind, sind die Heaps, die sie für dieselben Daten erstellen, im Allgemeinen unterschiedlich.

Nachdem man ein allgemeines Verständnis von Heaps hat, ist die Heap-Sortierung eine Selbstverständlichkeit.

Algorithmusübersicht/Ideen

Wir brauchen eine aufsteigende Reihenfolge, was sollen wir tun? Wir können einen Min-Heap erstellen und dann jedes Mal das Root-Element ausgeben. Diese Methode erfordert jedoch zusätzlichen Platz (andernfalls wird eine große Anzahl von Elementen verschoben und ihre Komplexität steigt auf O (n ^ 2)). Was ist, wenn wir an Ort und Stelle sortieren müssen (d. h. O(n)-Raumkomplexität ist nicht zulässig)?

Es gibt einen Weg. Wir können einen maximalen Heap erstellen und ihn dann rückwärts ausgeben, wobei wir an der letzten Position den Maximalwert und an der letzten Position den zweitgrößten Wert ausgeben ... Da jedes Mal das größte ausgegebene Element den ersten Platz freigibt Wir können solche Elemente einfach platzieren und benötigen keinen zusätzlichen Platz. Hübsche Idee, nicht wahr?

Das obige ist der detaillierte Inhalt vonBeispielanalyse eines Heap-Sortieralgorithmus in Java. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!