[GO] Python-Anfänger organisieren Heap-Sortierungen

Dies ist ein Memorandum

Ich habe es überhaupt nicht angefasst, seit ich die grundlegenden Informationen erhalten habe. Was ist also mit der Heap-Sortierung? Ich dachte, ich würde mir Notizen machen, während ich mein Wissen organisiere.

~~ Pakuru ~~ Ich werde zitieren

Es ist nicht unmöglich, einen Algorithmus von Grund auf neu zu erstellen, aber ehrlich gesagt ist es schwierig, deshalb habe ich ihn auf der Website [Referenz: A] und mir selbst zitiert. Ich werde es organisieren, während ich es zerlege.

Was ist Heap-Sortierung überhaupt?

Ich habe die allgemeinen Regeln mit einem Bild niedergeschrieben ~~ Ich weiß nicht, warum ich über so eine komplizierte Sache nachgedacht habe, aber ~~ Es scheint, dass es aufgrund der Bedienung des Arrangements einfach ist, auf und ab zu arbeiten. Es scheint, dass die Baumstruktur auch in Oracle DB verwendet wird (denken Sie daran), und die Effizienz der Datensuche scheint gut zu sein.

Ich habe es in einer besonderen Notiz geschrieben, weil ich denke, dass es drei Punkte gibt, an die man sich erinnern muss.

Körper

Eine Funktion des Heap-Sortierkörpers. Wenn Sie hier ein Array als Argument einfügen, wird es sortiert

heap_sort.py

def heap_sort(array):
    i = 0
    n = len(array)
    #Heap konfigurieren
    while(i < n):
        upheap(array, i)
        i += 1
    while(i > 1):#Von n bis 0
        #Holen Sie sich den Maximalwert vom Heap
        i -= 1
        array[0] , array[i] = array[i] , array[0]
        
        #Den Haufen rekonstruieren
        downheap(array, i-1)

Wenn Sie das Array erhalten, definieren Sie die Länge und den Index (wie gewohnt).

Führen Sie dann die Schleife von 0 bis zum letzten aus, während Sie den Index an upheao übergeben.

Vielleicht würde ich "für i in range (len (array))" schreiben. Ich benutze nur n oder hier. Ist es schwer zu lesen? ~~ Shiranai ~~

Und eine Downheep-Schleife. Ehrlich gesagt, der Grund, warum ich beschlossen habe, diesen Artikel zu schreiben. ~~ Es ist schwer zu verstehen ~~

Apropos, array[0] , array[i] = array[i] , array[0] Ist ein Tausch. Es scheint, dass Python so schreiben kann, also habe ich es versucht. Nur eine Zeile reicht aus.

Was ist Aufruhr?

upheap akzeptiert Arrays und Indizes als Argumente. Es empfängt Array und i vom Körper. Übrigens bedeutet "während n" "während n! = 0". Wenn es nicht 0 ist, ist es wahr.

upheap.py

def upheap(array, n):
    while n:
        parent = int((n - 1) / 2)
        #Versuchen Sie, den Wert von parent> child zu übernehmen
        if array[parent] < array[n]:
            array[n] , array[parent] = array[parent] , array[n]
            n = parent
        else:
            break

Dies ist die Aufgabe, eine kleine Zahl an das Kind weiterzugeben. Der Haufen ist im Grunde eine Regel, dass "Eltern klein sind, Kinder groß sind". Wenn Sie dies also nicht einmal tun, können Sie keine großen Zahlen an Kinder weitergeben. Wenn Sie also eine große Zahl an die Oberseite (Elternseite) übergeben haben, bereiten Sie sich darauf vor, eine große Zahl an das Kind zu übergeben.

before [1, 2, 3, 4, 5, 3, 2, 1, 4, 3, 4, 5, 0] upheap [5, 4, 5, 4, 4, 3, 2, 1, 1, 3, 3, 2, 0]

Es wird so sortiert

Was ist Downheep?

Downheap verwendet ein Array und einen Index als Argumente. Es empfängt Array und i-1 vom Körper.

downheap.py

#Wurzel[0]Der Haufen(0～n)Bewegen Sie sich in die optimale Position
def downheap(array, n):
    if n==0: return
    parent = 0
    while True:
        child = 2 * parent + 1 # array[n]Untergeordnetes Element von
        #Brechen Sie aus dem Element aus
        if child > n:
            break
        #Wenn sich ein Kind neben Ihnen und links <rechts befindet, schauen Sie sich das Kind rechts an
        if (child < n) and array[child] < array[child + 1]:
            child += 1
        #Tauschen Sie, wenn der Elternteil kleiner als das Kind ist
        if array[parent] < array[child]: 
            array[child] , array[parent] = array[parent] , array[child]
            
            parent = child; #Behält den Index nach dem Austausch bei
        else:
            break

Ich habe viele Notizen hinzugefügt, aber ist es nicht immer noch schwer zu verstehen? Voraussetzung ist die Eingabe dieser Funktion array[0] , array[i] = array[i] , array[0] tun. (Ich bin der fokussierte Teil) Auf diese Weise wird die höchste Nummer vor dem Sortieren an das niedrigste Kind übergeben, und die größte Nummer, die als nächstes übergeben wird, wird an das höchste Elternteil übergeben. Kann man sagen

before[1,2,3,4,5,3,2,1,4,3,4,5,0] upheap[5, 4, 5, 4, 4, 3, 2, 1, 1, 3, 3, 2, 0] [5, 4, 3, 4, 4, 2, 2, 1, 1, 3, 3, 0, 5] [4, 4, 3, 1, 4, 2, 2, 0, 1, 3, 3, 5, 5] [4, 4, 3, 1, 3, 2, 2, 0, 1, 3, 4, 5, 5] [4, 3, 3, 1, 3, 2, 2, 0, 1, 4, 4, 5, 5] [3, 3, 3, 1, 1, 2, 2, 0, 4, 4, 4, 5, 5] [3, 1, 3, 0, 1, 2, 2, 3, 4, 4, 4, 5, 5] [3, 1, 2, 0, 1, 2, 3, 3, 4, 4, 4, 5, 5] [2, 1, 2, 0, 1, 3, 3, 3, 4, 4, 4, 5, 5] [2, 1, 1, 0, 2, 3, 3, 3, 4, 4, 4, 5, 5] [1, 0, 1, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5] [1, 0, 1, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5] [0, 1, 1, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5]

Sehen Sie, dass sich die sortierten Zahlen in den niedrigeren Daten ansammeln, wenn der Fokusindex steigt? Dies gibt Ihnen eine schöne Sorte.

Schließlich

Dieses Mal habe ich die Algorithmen beim Schreiben eines Artikels organisiert, aber ich habe viele Fehler gemacht, also habe ich nachverfolgt und überprüft, ob meine Erklärung so korrekt wie möglich war. Diese Art von Form ist eine Studie, also hoffe ich, dass ich mit Selbstzufriedenheit weitermachen kann.

Referenz

[Referenz: A] https://webbibouroku.com/Blog/Article/py-heapsort ~~ Marupaku ~~ Ich habe es zitiert. Ich denke, dass die Hauptfamilie eine genauere Erklärung gibt. Wenn Sie also etwas nicht mögen, das schlecht gekaut wird, verstehen Sie es bitte bei der Hauptfamilie.