So implementieren Sie die Heap-Sortierung in Python (Codebeispiel)

Der Inhalt dieses Artikels befasst sich mit der Implementierung der Heap-Sortierung in Python (Codebeispiel). Ich hoffe, dass er für Sie hilfreich ist.

Heap-Sortierung

Heapsort bezieht sich auf einen Sortieralgorithmus, der unter Verwendung der Datenstruktur eines Heaps entwickelt wurde. Stapeln ist eine Struktur, die sich einem vollständigen Binärbaum annähert und gleichzeitig die Eigenschaften des Stapelns erfüllt: Das heißt, der Schlüsselwert oder Index eines untergeordneten Knotens ist immer kleiner (oder größer als) seines übergeordneten Knotens (aber es gibt). Es gibt keine Garantie dafür, dass alle linken Teilbäume kleiner sind als der rechte Teilbaum und umgekehrt. Man kann sagen, dass die Heap-Sortierung eine Auswahlsortierung ist, die das Konzept des Heaps zum Sortieren verwendet. In zwei Methoden unterteilt:

Großer oberer Heap: Der Wert jedes Knotens ist größer oder gleich dem Wert seines untergeordneten Knotens und wird im Heap-Sortieralgorithmus in aufsteigender Reihenfolge verwendet.

Klein oberer Heap: Der Wert jedes Knotens ist kleiner oder gleich dem Wert seines untergeordneten Knotens und wird im Heap-Sortierungsalgorithmus in absteigender Reihenfolge verwendet.

Die durchschnittliche Zeitkomplexität der Heap-Sortierung beträgt Ο(nlogn).

Algorithmusschritte

1. Erstellen Sie einen Heap H[0...n-1] (**Passen Sie die zu erstellenden untergeordneten Knoten an ein Heap **)

2. Vertauschen Sie den Kopf (Maximalwert) und den Schwanz des Heaps

3. Der Zweck besteht darin, die neuen Daten oben im Array an die entsprechende Position zu konvertieren.

4 Wiederholen Sie Schritt 2, bis die Heap-Größe 1 beträgt.

Python-Code-Implementierung

def buildMaxHeap(arr):
    import math
    for i in range(math.floor(len(arr)/2),-1,-1):#构建堆由下往上构建所以用-1
        heapify(arr,i)

def heapify(arr, i):
    left = 2*i+1
    right = 2*i+2
    largest = i
    if left < arrLen and arr[left] > arr[largest]:
        largest = left
    if right < arrLen and arr[right] > arr[largest]:
        largest = right

    if largest != i:
        swap(arr, i, largest)
        heapify(arr, largest)

def swap(arr, i, j):
    arr[i], arr[j] = arr[j], arr[i]

def heapSort(arr):
    global arrLen
    arrLen = len(arr)
    buildMaxHeap(arr)
    for i in range(len(arr)-1,0,-1):
        swap(arr,0,i)
        arrLen -=1 #每次踢掉求出的最大值
        heapify(arr, 0)
    return arr

Das obige ist der detaillierte Inhalt vonSo implementieren Sie die Heap-Sortierung in Python (Codebeispiel). Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!