Heap Art nicht funktioniert Python

Question

zu offenen Kurs ware algo Kurs Kapitel des MIT Bezug auf 4, habe ich die Stapelsortier nach dem psuedocode gegeben:

def heap_sort(A): 
    build_max_heap(A) 
    curr_heap_size = len(A) 
    while curr_heap_size: 
     A[0],A[curr_heap_size-1] = A[curr_heap_size-1],A 
     curr_heap_size -= 1 
     max_heapify(A,0) 
    return A 

build_max_heap ist garantiert korrekt sein, wie ich es überprüft mit Pythons heapq Bibliothek.

jedoch heap_sort scheint nicht richtig funktioniert,

test_array = [1,5,3,6,49,2,4,5,6] 
heap_sort(test_array) 
print(test_array) # --> [6,5,5,4,3,49,6,2,1] 

Komplett hier stapfte ich Kreuz mit Heap sort Python implementation geprüft und es scheint gleich zu sein ...

Hilfe schätzen würde, danke !

EDIT: Code für max_heapify und build_max_heap:

def max_heapify(A,i): 
    heap_size = len(A) 
    l,r = i*2+1,i*2+2 
    largest = l 
    if l < heap_size and A[l] > A[largest]: 
     largest = l 
    if r < heap_size and A[r] > A[largest]: 
     largest = r 
    if largest != i: 
     A[i],A[largest] = A[largest],A[i] 
     max_heapify(A,largest) 

def build_max_heap(A): 
    array_size = len(A) 
    for i in range(array_size // 2 ,-1,-1): 
     max_heapify(A,largest) 

Answer 1

Sie haben ein paar Fehler in Ihrem Code, der es schwieriger gemacht, Ihren Fall, sie zu regenerieren und die Lösung für Ihr spezielles Thema finden, aber hier geht es.

Zuerst enthält Ihr Code einen Syntaxfehler in der Funktion heap_sort, insbesondere wenn Sie versuchen, das erste und das letzte Element von A zu tauschen. Auf der rechten Seite dieser Zuweisung ist der zweite Wert A, obwohl es sollte sei A [0].

Zweitens, Ihre Verwendung der Variable am größten in build_max_heap impliziert entweder, dass die größte eine globale Variablendeklaration ist, die Sie in Ihrer Frage nicht angegeben haben, oder Sie stattdessen i verwenden möchten. Ich nahm an, dass es der zweite Fall war, und da ich einen funktionierenden heap_sort basierend auf dem von Ihnen bereitgestellten Code habe, denke ich, dass meine Annahme richtig war.

Drittens initialisieren Sie in max_heapify am größten auf l, obwohl Sie es mit i initialisieren sollten. Ich glaube, Sie werden dies als einen trivialen Fehler empfinden, da Sie weiter unten dieselbe Funktion erwarten, dass Sie klar erwarten, dass der Wert des größten gleich dem von i ist.

Schließlich ist Ihr wichtigster Fehler, dass Sie das gesamte Array weiterleiten und eine Array-Länge verwenden, die niemals abnimmt (dh es ist immer die Anfangslänge von test_array). Der von Ihnen verwendete Algorithmus findet das maximale Element des angegebenen Array und schließen Sie es vom Rest der Struktur aus. Auf diese Weise haben Sie ein Array, das immer kleiner wird, während es sein größtes Element an das Ende sendet (dh knapp über seine Reichweite/Länge) Aber da Sie nie die Größe des Arrays verringern, und seine Länge ist kontinuierlich berechnet als len (test_array), wird es niemals wie erwartet funktionieren.

Es gibt zwei Ansätze, die Ihr Problem lösen können. Option 1 wird in heap_sort an max_heapify einer kürzeren Version von A übergeben. Insbesondere sollten Sie A [: curr_heap_size] bei jeder Iteration der Schleife übergeben. Diese Methode kann zwar funktionieren, ist aber nicht wirklich platzsparend, da Sie jedes Mal eine neue Liste erstellen. Stattdessen können Sie curr_heap_size als Argument an die Funktionen build_max_heap und max_heapify übergeben und davon ausgehen, dass es sich um die Länge handelt. (d. h. im Gegensatz zu len (A))

Unten ist eine funktionierende heap_sort-Implementierung, basierend auf Ihrem Code. Ich habe nur die Fehler korrigiert, die ich oben aufgeführt habe.

def max_heapify(A, heap_size, i): 
    l,r = i*2+1,i*2+2 
    largest = i 
    if l < heap_size and A[l] > A[largest]: 
     largest = l 
    if r < heap_size and A[r] > A[largest]: 
     largest = r 
    if largest != i: 
     A[i], A[largest] = A[largest], A[i] 
     max_heapify(A, heap_size, largest) 

def build_max_heap(A, array_size): 
    for i in range(array_size // 2 ,-1,-1): 
     max_heapify(A, array_size, i) 

def heap_sort(A): 
    curr_heap_size = len(A) 
    build_max_heap(A, curr_heap_size) 
    while curr_heap_size > 0: 
     A[0], A[curr_heap_size-1] = A[curr_heap_size-1], A[0] 
     curr_heap_size -= 1 
     max_heapify(A, curr_heap_size, 0) 
    return A