Haufensort

Heap-Sortierung

Heap-Sortierung ist ein Sortieralgorithmus, der auf der Datenstruktur eines Heaps basiert und eine Auswahlsortierung ist. Die durchschnittliche Zeitkomplexität beträgt O (nlogn), was ebenfalls eine instabile Sortierung ist. Lassen Sie uns zunächst kurz die Heap-Struktur verstehen.

Heap

Ein Heap ist ein vollständiger Binärbaum mit den folgenden Eigenschaften: Der Wert jedes Knotens ist größer oder gleich zu seinen linken und rechten untergeordneten Knoten Der Wert eines Knotens wird als großer oberer Heap bezeichnet. Oder der Wert jedes Knotens ist kleiner oder gleich dem Wert seiner linken und rechten untergeordneten Knoten, was als kleiner oberer Heap bezeichnet wird.

Empfohlener Kurs: PHP-Tutorial.

Wie unten gezeigt:

Gleichzeitig nummerieren wir die Knoten im Heap schichtweise, um diese logische Struktur abzubilden Im Array sieht es so aus

Das Array ist logischerweise eine Heap-Struktur. Wir verwenden eine einfache Formel, um die Definition eines Heaps zu beschreiben:

Groß oberer Heap: arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]

Kleiner oberer Heap: arr[i]

Die Grundidee der Heap-Sortierung ist:

Konstruieren Sie die zu seinde Sequenz sortiert Es bildet einen großen oberen Heap. Zu diesem Zeitpunkt ist der Maximalwert der gesamten Sequenz der Wurzelknoten an der Spitze des Heaps. Tauschen Sie es mit dem letzten Element aus, dann ist der letzte Wert der Maximalwert. Rekonstruieren Sie dann die verbleibenden n-1 Elemente in einen Heap, sodass der nächstkleinere Wert von n Elementen erhalten wird. Wenn Sie dies wiederholt ausführen, erhalten Sie eine geordnete Sequenz

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