So sortieren Sie im Heapsort

1. Erstellen Sie den anfänglichen Heap:

Beim Initialisieren des Heaps werden alle Nicht-Blattknoten gefiltert.

Der Index des letzten nicht-terminalen Elements ist [n/2] abgerundet, daher muss die Filterung nur beim [n/2]-ten abgerundeten Element beginnen und von hinten nach vorne angepasst werden.

Erstellen Sie beispielsweise bei einem gegebenen Array zunächst einen vollständigen Binärbaum basierend auf den Array-Elementen.

Beginnend mit dem letzten Nicht-Blattknoten werden dann jedes Mal Vergleiche und Austausche vom übergeordneten Knoten, vom linken untergeordneten Knoten und vom rechten untergeordneten Knoten durchgeführt. Der Austausch kann dazu führen, dass der untergeordnete Knoten die Eigenschaften des Heaps nicht erfüllt , also jedes Mal Nach diesem Austausch müssen die ausgetauschten untergeordneten Knoten neu angepasst werden.

2. Führen Sie eine Heap-Sortierung durch:

Nachdem Sie den ersten Heap erstellt haben, können Sie sortieren.

Heap-Sortierung ist eine Auswahlsortierung. Der zunächst erstellte Heap ist der anfängliche ungeordnete Bereich.

Wenn die Sortierung beginnt, wird das oberste Element des Heaps zuerst ausgegeben (da es der höchste Wert ist) und das oberste Element des Heaps und das letzte Element werden ausgetauscht. Auf diese Weise wird die n-te Position (). Das heißt, die letzte Position wird als geordneter Bereich verwendet, und die vorherigen n-1-Positionen sind immer noch ungeordnete Bereiche. Tauschen Sie nach Erhalt des Heaps die oberen und letzten Elemente des Heaps aus, um die Länge zu erhalten der geordneten Fläche wird 2. . .

Setzen Sie diesen Vorgang fort, passen Sie die verbleibenden Elemente erneut im Heap an und geben Sie dann das oberste Element des Heaps in den sortierten Bereich aus. Jeder Austausch ergibt -1 für den ungeordneten Bereich und +1 für den geordneten Bereich. Dieser Vorgang wird wiederholt, bis die Länge des geordneten Bereichs auf n-1 anwächst und die Sortierung abgeschlossen ist.

3. Beispiel für die Heap-Sortierung:

Erstellen Sie zunächst die anfängliche Heap-Struktur wie gezeigt:

Dann , Tauschen Sie das Element oben im Heap und das letzte Element aus. Zu diesem Zeitpunkt wird die letzte Position als geordneter Bereich verwendet (der geordnete Bereich wird gelb angezeigt) und dann den Heap der anderen ungeordneten Bereiche anpassen Tauschen Sie beim großen oberen Heap die Position des vorletzten Elements aus...

Wiederholen Sie diesen Vorgang:

Endlich ist die geordnete Flächenerweiterung abgeschlossen. Das heißt, die Sortierung ist abgeschlossen:

Aus dem Sortiervorgang ist ersichtlich, dass wenn Sie Wenn Sie eine aufsteigende Reihenfolge erhalten möchten, erstellen Sie einen großen oberen Heap. Wenn Sie eine absteigende Reihenfolge erhalten möchten, erstellen Sie einen kleinen oberen Heap.

Das obige ist der detaillierte Inhalt vonSo sortieren Sie im Heapsort. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!