heapsort

Heapsort – Pyramidensortierung. Zeitliche Komplexität des Algorithmus – O(n log n), schnell, oder? Ich würde das Sortieren das Sortieren fallender Kieselsteine nennen. Es scheint mir, dass man es am einfachsten visuell erklären kann.

Die Eingabe ist eine Liste von Zahlen, zum Beispiel:
5, 0, 7, 2, 3, 9, 4

Von links nach rechts wird eine Datenstruktur erstellt – ein Binärbaum, oder wie ich es nenne – Pyramide. Pyramidenelemente können maximal zwei untergeordnete Elemente, aber nur ein oberstes Element haben.

Lassen Sie uns einen Binärbaum erstellen:
⠀⠀5
⠀0⠀7
2 3 9 4

Wenn Sie die Pyramide längere Zeit betrachten, können Sie erkennen, dass es sich nur um Zahlen aus einer Reihe handelt, die nacheinander auftauchen. Die Anzahl der Elemente in jeder Etage wird mit zwei multipliziert.

Als nächstes beginnt der Spaß: Sortieren wir die Pyramide von unten nach oben mit der Methode der fallenden Kieselsteine (aufhäufen). Mit dem Sortieren könnte man ab der letzten Etage beginnen (2 3 9 4), aber es hat keinen Sinn, weil Es gibt keine Etage darunter, in die man fallen könnte.

Daher beginnen wir, Elemente aus der vorletzten Etage (0 7) fallen zu lassen
⠀⠀5
⠀0⠀7
2 3 9 4

Das erste fallende Element wird von rechts ausgewählt, in unserem Fall ist es 7, dann schauen wir uns an, was darunter liegt, und darunter sind 9 und 4, neun ist größer als vier, und auch neun ist größer als Sieben! Wir lassen 7 auf 9 fallen und heben 9 auf Platz 7.
⠀⠀5
⠀0⠀9
2 3 7 4

Als nächstes verstehen wir, dass die Sieben nirgendwo tiefer fallen kann, und gehen weiter zur Zahl 0, die sich im vorletzten Stockwerk auf der linken Seite befindet:
⠀⠀5
⠀0⠀9
2 3 7 4

Mal sehen, was sich darunter verbirgt – 2 und 3, zwei ist kleiner als drei, drei ist mehr als null, also vertauschen wir null und drei:
⠀⠀5
⠀3⠀9
2 0 7 4

Wenn Sie das Ende der Etage erreichen, gehen Sie in die darüber liegende Etage und lassen Sie dort, wenn möglich, alles ab.
Das Ergebnis ist eine Datenstruktur – ein Heap, nämlich Max Heap, weil Oben ist das größte Element:
⠀⠀9
⠀3⠀7
2 0 5 4

Wenn Sie es in eine Array-Darstellung zurückführen, erhalten Sie eine Liste:
[9, 3, 7, 2, 0, 5, 4]

Daraus können wir schließen, dass wir durch Vertauschen des ersten und letzten Elements die erste Zahl an der endgültigen sortierten Position erhalten, nämlich 9 sollte am Ende der sortierten Liste stehen, Plätze vertauschen:
[4, 3, 7, 2, 0, 5, 9]

Sehen wir uns einen Binärbaum an:
⠀⠀4
⠀3⠀7
2 0 5 9

Das Ergebnis ist eine Situation, in der der untere Teil des Baums sortiert ist. Sie müssen lediglich 4 an der richtigen Position ablegen, den Algorithmus wiederholen, aber die bereits sortierten Zahlen, nämlich 9, nicht berücksichtigen:
⠀⠀4
⠀3⠀7
2 0 5 9

⠀⠀7
⠀3⠀4
2 0 5 9

⠀⠀7
⠀3⠀5
2 0 4 9

Es stellte sich heraus, dass wir, nachdem wir 4 verloren hatten, die nächstgrößte Zahl nach 9 erhöht hatten – 7. Vertauschen Sie die letzte unsortierte Zahl (4) und die größte Zahl (7)
⠀⠀4
⠀3⠀5
2 0 7 9

Es stellt sich heraus, dass wir jetzt zwei Zahlen an der richtigen Endposition haben:
4, 3, 5, 2, 0, 7, 9

Als nächstes wiederholen wir den Sortieralgorithmus und ignorieren die bereits sortierten. Am Ende erhalten wir ein Heap Typ:
⠀⠀0
⠀2⠀3
4 5 7 9

Oder als Liste:
0, 2, 3, 4, 5, 7, 9

Implementierung

Der Algorithmus ist normalerweise in drei Funktionen unterteilt:

Einen Heap erstellen
Sifting-Algorithmus (Heapify)
Ersetzen des letzten unsortierten Elements durch das erste

Der Heap wird erstellt, indem die vorletzte Zeile des Binärbaums mithilfe der Heapify-Funktion von rechts nach links bis zum Ende des Arrays durchlaufen wird. Als nächstes im Zyklus erfolgt die erste Ersetzung der Zahlen, danach fällt/bleibt das erste Element an Ort und Stelle, wodurch das größte Element an die erste Stelle fällt, der Zyklus wird mit einer Verringerung der Teilnehmerzahl um eins wiederholt, weil Nach jedem Durchlauf bleiben sortierte Zahlen am Ende der Liste.

Heapsort-Beispiel in Ruby:






module Colors



    BLUE = "\033[94m"



    RED = "\033[31m"



    STOP = "\033[0m"



end







def heapsort(rawNumbers)



    numbers = rawNumbers.dup







    def swap(numbers, from, to)



        temp = numbers[from]



        numbers[from] = numbers[to]



        numbers[to] = temp



    end







    def heapify(numbers)



        count = numbers.length()



        lastParentNode = (count - 2) / 2







        for start in lastParentNode.downto(0)



            siftDown(numbers, start, count - 1)



            start -= 1 



        end







        if DEMO



            puts "--- heapify ends ---"



        end



    end







    def siftDown(numbers, start, rightBound)      



        cursor = start



        printBinaryHeap(numbers, cursor, rightBound)







        def calculateLhsChildIndex(cursor)



            return cursor * 2 + 1



        end







        def calculateRhsChildIndex(cursor)



            return cursor * 2 + 2



        end            







        while calculateLhsChildIndex(cursor) <= rightBound



            lhsChildIndex = calculateLhsChildIndex(cursor)



            rhsChildIndex = calculateRhsChildIndex(cursor)







            lhsNumber = numbers[lhsChildIndex]



            biggerChildIndex = lhsChildIndex







            if rhsChildIndex <= rightBound



                rhsNumber = numbers[rhsChildIndex]



                if lhsNumber < rhsNumber



                    biggerChildIndex = rhsChildIndex



                end



            end







            if numbers[cursor] < numbers[biggerChildIndex]



                swap(numbers, cursor, biggerChildIndex)



                cursor = biggerChildIndex



            else



                break



            end



            printBinaryHeap(numbers, cursor, rightBound)



        end



        printBinaryHeap(numbers, cursor, rightBound)



    end







    def printBinaryHeap(numbers, nodeIndex = -1, rightBound = -1)



        if DEMO == false



            return



        end



        perLineWidth = (numbers.length() * 4).to_i



        linesCount = Math.log2(numbers.length()).ceil()



        xPrinterCount = 1



        cursor = 0



        spacing = 3



        for y in (0..linesCount)



            line = perLineWidth.times.map { " " }



            spacing = spacing == 3 ? 4 : 3



            printIndex = (perLineWidth / 2) - (spacing * xPrinterCount) / 2



            for x in (0..xPrinterCount - 1)



                if cursor >= numbers.length



                    break



                end



                if nodeIndex != -1 && cursor == nodeIndex



                    line[printIndex] = "%s%s%s" % [Colors::RED, numbers[cursor].to_s, Colors::STOP]



                elsif rightBound != -1 && cursor > rightBound



                    line[printIndex] = "%s%s%s" % [Colors::BLUE, numbers[cursor].to_s, Colors::STOP]



                else



                    line[printIndex] = numbers[cursor].to_s



                end



                cursor += 1



                printIndex += spacing



            end



            print line.join()



            xPrinterCount *= 2           



            print "\n"            



        end



    end







    heapify(numbers)



    rightBound = numbers.length() - 1







    while rightBound > 0



        swap(numbers, 0, rightBound)   



        rightBound -= 1



        siftDown(numbers, 0, rightBound)     



    end







    return numbers



end







numbersCount = 14



maximalNumber = 10



numbers = numbersCount.times.map { Random.rand(maximalNumber) }



print numbers



print "\n---\n"







start = Time.now



sortedNumbers = heapsort(numbers)



finish = Time.now



heapSortTime = start - finish







start = Time.now



referenceSortedNumbers = numbers.sort()



finish = Time.now



referenceSortTime = start - finish







print "Reference sort: "



print referenceSortedNumbers



print "\n"



print "Reference sort time: %f\n" % referenceSortTime



print "Heap sort:      "



print sortedNumbers



print "\n"



if DEMO == false



    print "Heap sort time:      %f\n" % heapSortTime



else



    print "Disable DEMO for performance measure\n"



end







if sortedNumbers != referenceSortedNumbers



    puts "Validation failed"



    exit 1



else



    puts "Validation success"



    exit 0



end

Dieser Algorithmus ist ohne Visualisierung nicht leicht zu verstehen, daher empfehle ich als Erstes, eine Funktion zu schreiben, die die aktuelle Ansicht des Binärbaums druckt.