Python-Heap-Sortierung

1. Heap-Sortieralgorithmus in Python
2. Implementieren Sie den Heap-Sortieralgorithmus in Python

Dieses Tutorial zeigt die Implementierung des Heap-Sort-Algorithmus in Python.

Heap-Sortieralgorithmus in Python

Heapsort ist ein robuster Algorithmus zum Sortieren von Arrays und Listen in Python. Es ist beliebt, weil es sehr schnell ist und keinen zusätzlichen Platz benötigt, wie Merge Sort und Quick Sort.

Die Zeitkomplexität von Heap Sort ist O(n*log(n)).

Die Heap-Sortierung ist ein In-Place-Algorithmus, der keine Datenstrukturen mehr erstellt, um die Zwischenstände von Daten zu speichern. Stattdessen nimmt es Änderungen in unserem ursprünglichen Array vor.

Daher sparen wir viel Platz, wenn die Daten sehr groß sind.

Der einzige Nachteil dieses Algorithmus ist, dass er sehr instabil ist. Wenn wir in unserem Array mehrere Elemente mit demselben Wert an verschiedenen Indizes haben, ändern sich ihre Positionen während des Sortierens.

Der Heap-Sortieralgorithmus funktioniert, indem er rekursiv entweder einen min- oder einen max-Heap erstellt, den Root-Knoten herausnimmt, ihn am ersten unsortierten Index in unserem Array platziert und das letzte Heap-Element in den Root-Knoten umwandelt.

Dieser Vorgang wird rekursiv wiederholt, bis nur noch ein einziger Knoten in unserem Heap übrig bleibt. Am Ende wird das letzte Heap-Element am letzten Index unseres Arrays platziert.

Wenn wir eine Sekunde darüber nachdenken, ähnelt dieser Prozess dem Selection-Sort-Algorithmus, da wir entweder die größten oder die kleinsten Werte nehmen und sie an die Spitze unseres sortierten Arrays setzen.

Implementieren Sie den Heap-Sortieralgorithmus in Python

Wir werden uns zuerst mit der Implementierung der Funktion build_heap() befassen, die das ursprüngliche Array, die Länge des Arrays und den Index unseres übergeordneten Knotens übernimmt. Wenn wir uns hier ein Array ansehen, befindet sich der Index für den letzten übergeordneten Knoten bei (n//2 - 1) in unserem Array.

In ähnlicher Weise ist der Index für das linke Kind dieses bestimmten Elternteils 2*parent_index + 1, und der Index für das rechte Kind ist 2*parent_index + 2.

In diesem Beispiel versuchen wir, einen Max-Heap zu erstellen. Das bedeutet, dass jeder übergeordnete Knoten größer sein muss als seine untergeordneten Knoten.

Dazu beginnen wir beim letzten übergeordneten Knoten und bewegen uns nach oben zum Wurzelknoten unseres Heaps. Wenn wir einen Min-Heap erstellen möchten, möchten wir, dass alle unsere übergeordneten Knoten kleiner sind als ihre untergeordneten Knoten.

Diese build_heap()-Funktion prüft, ob der linke oder der rechte Kindknoten größer als der aktuelle Elternknoten ist und tauscht den größten Knoten mit dem Elternknoten aus.

Diese Funktion ruft sich selbst rekursiv auf, da wir den vorherigen Prozess inkrementell für alle übergeordneten Knoten in unserem Heap wiederholen möchten.

Das folgende Code-Snippet demonstriert eine funktionierende Implementierung der oben erwähnten Funktion built_heap() in Python.

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)

Jetzt haben wir eine Funktion, die den maximalen Wert in unserem Array nimmt und ihn auf der Wurzel unseres Heaps platziert. Wir brauchen eine Funktion, die das unsortierte Array nimmt, die Funktion build_heap() aufruft und Elemente aus dem Heap extrahiert.

Das folgende Code-Snippet demonstriert die Implementierung der Funktion heapSort() in Python.

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)

Wir rufen inkrementell die Funktion build_heap() jedes übergeordneten Knotens in unserem Array auf. Beachten Sie, dass wir length//2-1 als Startindex und -1 als Endindex angeben, mit einem Schritt von -1.

Dies bedeutet, dass wir vom letzten übergeordneten Knoten ausgehen und unseren Index schrittweise um 1 verringern, bis wir den Wurzelknoten erreichen.

Die zweite for-Schleife extrahiert Elemente aus unserem Heap. Es beginnt auch beim letzten Index und endet beim ersten Index unseres Arrays.

In dieser Schleife vertauschen wir das erste und das letzte Element unseres Arrays und führen die Funktion build_heap() auf dem neu sortierten Array aus, indem wir 0 als Root-Index übergeben.

Jetzt haben wir unser Programm geschrieben, um die Heap-Sortierung in Python zu implementieren. Es ist an der Zeit, ein Array zu sortieren und den oben geschriebenen Code zu testen.

arr = [5, 3, 4, 2, 1, 6]
heapSort(arr)
print("Sorted array :", arr)

Ausgang:

Sorted array : [1, 2, 3, 4, 5, 6]

Wie wir sehen können, ist unser Array vollständig sortiert. Das bedeutet, dass unser Code einwandfrei funktioniert.

Wenn wir in absteigender Reihenfolge sortieren möchten, können wir anstelle des oben implementierten Max-Heaps einen Min-Heap erstellen.

In diesem Artikel wird min-heap nicht erklärt, da bereits zu Beginn dieses Tutorials erläutert wurde, was ein min-heap ist.

Unser Programm funktioniert wie folgt. Der folgende Block zeigt den Status unseres Arrays in jeder Phase der Codeausführung.

Original Array [5, 3, 4, 2, 1, 6] # input array
Building Heap [5, 3, 6, 2, 1, 4] # after build_heap() pass 1
Building Heap [5, 3, 6, 2, 1, 4] # after build_heap() pass 2
Building Heap [6, 3, 5, 2, 1, 4] # after build_heap() pass 3
Extracting Elements [6, 3, 5, 2, 1, 4] # before swapping and build_heap pass 1
Extracting Elements [5, 3, 4, 2, 1, 6] # before swapping and build_heap pass 2
Extracting Elements [4, 3, 1, 2, 5, 6] # before swapping and build_heap pass 3
Extracting Elements [3, 2, 1, 4, 5, 6] # before swapping and build_heap pass 4
Extracting Elements [2, 1, 3, 4, 5, 6] # before swapping and build_heap pass 5
Sorted array : [1, 2, 3, 4, 5, 6] # after swapping and build_heap pass 5

Die Funktion build_heap() wird 3 Mal ausgeführt, weil es nur 3 Elternknoten in unserem Heap gibt.

Danach nimmt unsere Elementextraktionsphase das erste Element, tauscht es mit dem letzten Element aus und führt die Funktion build_heap() erneut aus. Dieser Vorgang wird für Länge - 1 wiederholt, und unser Array wird sortiert.