HOWTO · Python
Python-Heap-Sortierung
Die Implementierung des Heap-Sortieralgorithmus in Python kann in zwei Teile unterteilt werden; eine Funktion, die entweder einen Min-Heap oder einen Max-Heap erstellt, und eine Funktion, die den eigentlichen Heap-Sortieralgorithmus implementiert.
Auf dieser Seite
In diesem Tutorial erfahren Sie, wie der Heapsort-Algorithmus funktioniert und wie Sie ihn in Python implementieren – von der Indexarithmetik hinter der Heap-Konstruktion bis zu einer Schritt-für-Schritt-Verfolgung einer Beispielliste.
Der Heapsort-Algorithmus in Python
Heapsort ist ein vergleichsbasierter Algorithmus, der eine Liste sortiert, indem er sie als binären Heap organisiert. Ein Heap ist ein vollständiger Binärbaum, der in flachen Array-Positionen gespeichert wird: In einem Max-Heap ist jeder Elternknoten größer oder gleich seinen Kindern, während in einem Min-Heap jeder Elternknoten kleiner oder gleich seinen Kindern ist.
Der Algorithmus wiederholt zwei Phasen:
- Erstellen Sie einen Heap aus den unsortierten Daten, sodass der Extremwert an der Wurzel liegt (der maximale Wert für einen Max-Heap).
- Tauschen Sie die Wurzel mit dem letzten Element des noch unsortierten Bereichs, verkleinern Sie den Heap um eine Position und stellen Sie die Heap-Eigenschaft an der neuen Wurzel wieder her.
Bei jeder Wiederholung wird ein Wert an seiner endgültigen Position abgelegt, bis nur noch ein einziger Knoten im Heap verbleibt. In diesem Sinne ähnelt Heapsort dem Selectionsort: Jeder Durchlauf wählt den aktuell größten Wert aus und platziert ihn zwischen dem unsortierten Heap-Bereich und dem bereits sortierten Ende des Arrays.
Die Zeitkomplexität von Heapsort beträgt O(n*log(n)) im besten, durchschnittlichen und schlechtesten Fall, da jede der n Extraktionen höchstens O(log n) Arbeit erfordert, um den Heap wiederherzustellen. Die Sortierung verändert die Eingabeliste direkt, statt eine zweite Datenstruktur aufzubauen, wodurch der Speicherverbrauch bei großen Eingaben gering bleibt. Beachten Sie, dass die unten gezeigte rekursive Heap-Reparaturfunktion weiterhin bis zu O(log n) zusätzlichen Platz auf dem Aufrufstapel verbraucht; wenn Sie den Sift-down-Schritt als Schleife schreiben, reduziert sich dieser Wert auf O(1).
Der Hauptnachteil von Heapsort ist, dass er nicht stabil ist. Wenn mehrere Elemente denselben Wert haben, kann sich ihre relative Reihenfolge während der Sortierung ändern.
Heapsort in Python implementieren
Die Implementierung ist in zwei Funktionen aufgeteilt: build_heap() stellt die Heap-Eigenschaft unterhalb eines Elternknotens wieder her, und heapSort() steuert die Aufbauphase und die Extraktionsphase.
Die Funktion build_heap() erhält das Array, die Länge des aktiven Heap-Bereichs und den Index des zu prüfenden Elternknotens. In einem flachen Array befindet sich der letzte Elternknoten am Index length//2 - 1, das linke Kind eines Elternknotens liegt bei 2*parent_index + 1 und das rechte Kind bei 2*parent_index + 2.
Für einen Max-Heap vergleicht die Funktion den Elternknoten mit beiden Kindern und tauscht ihn mit dem größeren Kindknoten, wenn ein Kind größer ist. Da der Tausch die Heap-Eigenschaft weiter unten verletzen kann, ruft build_heap() sich selbst für den betroffenen Teilbaum auf, sodass der verschobene Wert weiter absinkt, bis jeder darunterliegende Elternknoten wieder gültig ist.
Der Code und die angezeigten Bezeichnungen oder Ausgaben in diesem Abschnitt bleiben auf Englisch.
def build_heap(arr, length, parent_index):
largest_index = parent_index
left_index = 2 * parent_index + 1
right_index = 2 * parent_index + 2
if left_index < length and arr[parent_index] < arr[left_index]:
largest_index = left_index
if right_index < length and arr[largest_index] < arr[right_index]:
largest_index = right_index
if largest_index != parent_index:
arr[parent_index], arr[largest_index] = arr[largest_index], arr[parent_index]
build_heap(arr, length, largest_index)
Die Funktion heapSort() führt die beiden oben beschriebenen Phasen aus. Ihre erste Schleife ruft build_heap() für jeden Elternindex von length//2 - 1 abwärts bis 0 auf und wandelt dadurch das gesamte Array in einen Max-Heap um. Ihre zweite Schleife führt die Extraktion aus: Tauschen Sie die Wurzel in den letzten unsortierten Platz, kürzen Sie den aktiven Bereich und reparieren Sie den Heap erneut ab Index 0.
def heapSort(arr):
length = len(arr)
for parent_index in range(length // 2 - 1, -1, -1):
build_heap(arr, length, parent_index)
for element_index in range(length - 1, 0, -1):
arr[element_index], arr[0] = arr[0], arr[element_index]
build_heap(arr, element_index, 0)
Führen Sie dieses vollständige Programm aus, um eine Beispielliste zu sortieren:
def build_heap(arr, length, parent_index):
largest_index = parent_index
left_index = 2 * parent_index + 1
right_index = 2 * parent_index + 2
if left_index < length and arr[parent_index] < arr[left_index]:
largest_index = left_index
if right_index < length and arr[largest_index] < arr[right_index]:
largest_index = right_index
if largest_index != parent_index:
arr[parent_index], arr[largest_index] = arr[largest_index], arr[parent_index]
build_heap(arr, length, largest_index)
def heapSort(arr):
length = len(arr)
for parent_index in range(length // 2 - 1, -1, -1):
build_heap(arr, length, parent_index)
for element_index in range(length - 1, 0, -1):
arr[element_index], arr[0] = arr[0], arr[element_index]
build_heap(arr, element_index, 0)
arr = [5, 3, 4, 2, 1, 6]
heapSort(arr)
print("Sorted array :", arr)
Sorted array : [1, 2, 3, 4, 5, 6]
Das Array ist anschließend vollständig in aufsteigender Reihenfolge sortiert. Das unveränderte Beispiel gibt die englische Bezeichnung Sorted array gefolgt von der sortierten Liste aus. Um mit demselben Extraktionsmuster in absteigender Reihenfolge zu sortieren, erstellen Sie einen Min-Heap anstelle eines Max-Heaps: Drehen Sie die beiden Vergleiche in build_heap() um, sodass der Elternknoten mit dem kleineren Kindknoten getauscht wird. Jede Extraktion legt dann das aktuelle Minimum am Ende des Arrays ab, was ein absteigend sortiertes Ergebnis ergibt.
Ein Heapsort-Beispiel nachvollziehen
Wenn Sie das Programm mit arr = [5, 3, 4, 2, 1, 6] ausführen, ergeben sich die folgenden Zustände:
- Eingabe:
[5, 3, 4, 2, 1, 6] - Aufbaudurchlauf 1 (
parent_index = 2):[5, 3, 6, 2, 1, 4]— der Wert 4 sinkt unter seinen größeren Kindknoten 6 - Aufbaudurchlauf 2 (
parent_index = 1):[5, 3, 6, 2, 1, 4]— kein Tausch, da 3 bereits größer als beide Kindknoten ist - Aufbaudurchlauf 3 (
parent_index = 0):[6, 3, 5, 2, 1, 4]— das Array ist jetzt ein gültiger Max-Heap - Extraktionsdurchlauf 1:
[5, 3, 4, 2, 1, 6]— 6 wird am letzten Index abgelegt - Extraktionsdurchlauf 2:
[4, 3, 1, 2, 5, 6] - Extraktionsdurchlauf 3:
[3, 2, 1, 4, 5, 6] - Extraktionsdurchlauf 4:
[2, 1, 3, 4, 5, 6] - Extraktionsdurchlauf 5:
[1, 2, 3, 4, 5, 6]— sortiert
Jede Extraktionszeile zeigt den Zustand nach dem Tausch und der Heap-Reparatur für diesen Durchlauf. Die Aufbauphase ruft build_heap() dreimal auf, weil der Heap mit sechs Elementen drei Elternknoten enthält, und die Extraktionsphase ruft ihn einmal für jeden der length - 1 Tausch- und Reparaturzyklen auf.
