heapsort

Heapsort – tri pyramidal. Complexité temporelle de l’algorithme – O(n log n), vite, non ? J’appellerais ce tri le tri des cailloux qui tombent. Il me semble que la façon la plus simple de l’expliquer est visuellement.

L’entrée est une liste de nombres, par exemple :
5, 0, 7, 2, 3, 9, 4

De gauche à droite, une structure de données est créée : un arbre binaire, ou comme je l’appelle : un arbre binaire. pyramide. Les éléments pyramidaux peuvent avoir un maximum de deux éléments enfants, mais un seul élément supérieur.

Créons un arbre binaire :
⠀⠀5
⠀0⠀7
2 3 9 4

Si vous regardez la pyramide pendant longtemps, vous pouvez voir que ce ne sont que des nombres provenant d’un tableau, se succédant les uns après les autres, le nombre d’éléments dans chaque étage est multiplié par deux.

Ensuite, le plaisir commence : trions la pyramide de bas en haut en utilisant la méthode des cailloux tombants (tassifier). Le tri pourrait être lancé depuis le dernier étage (2 3 9 4), mais cela ne sert à rien car il n’y a pas d’étage en dessous où vous pourriez tomber.

Par conséquent, nous commençons à supprimer les éléments de l’avant-dernier étage (0 7)
⠀⠀5
⠀0⠀7
2 3 9 4

Le premier élément à tomber est sélectionné à droite, dans notre cas c’est 7, puis nous regardons ce qu’il y a en dessous, et en dessous se trouvent 9 et 4, neuf est supérieur à quatre, et neuf est également supérieur à Sept! Nous déposons 7 sur 9 et soulevons 9 à la place 7.
⠀⠀5
⠀0⠀9
2 3 7 4

Ensuite, on comprend que sept n’a nulle part où descendre plus bas, on passe au chiffre 0, qui se situe à l’avant-dernier étage à gauche :
⠀⠀5
⠀0⠀9
2 3 7 4

Voyons ce qu’il y a en dessous – 2 et 3, deux est inférieur à trois, trois est supérieur à zéro, donc on échange zéro et trois :
⠀⠀5
⠀3⠀9
2 0 7 4

Lorsque vous atteignez le bout de l’étage, allez à l’étage supérieur et déposez tout là-bas si vous le pouvez.
Le résultat est une structure de données – un tas, à savoir max tas, car en haut se trouve le plus grand élément :
⠀⠀9
⠀3⠀7
2 0 5 4

Si vous le renvoyez à une représentation matricielle, vous obtenez une liste :
[9, 3, 7, 2, 0, 5, 4]

De là, nous pouvons conclure qu’en échangeant le premier et le dernier élément, nous obtenons le premier nombre dans la position triée finale, à savoir que 9 doit être à la fin de la liste triée, échangez les places :
[4, 3, 7, 2, 0, 5, 9]

Regardons un arbre binaire :
⠀⠀4
⠀3⠀7
2 0 5 9

Le résultat est une situation dans laquelle la partie inférieure de l’arbre est triée, il suffit d’en déposer 4 à la bonne position, de répéter l’algorithme, mais de ne pas prendre en compte les nombres déjà triés, à savoir 9 :
⠀⠀4
⠀3⠀7
2 0 5 9

⠀⠀7
⠀3⠀4
2 0 5 9

⠀⠀7
⠀3⠀5
2 0 4 9

Il s’est avéré que nous, après avoir perdu 4, avons soulevé le deuxième plus grand nombre après 9 – 7. Échangez le dernier numéro non trié (4) et le plus grand nombre (7)
⠀⠀4
⠀3⠀5
2 0 7 9

Il s’avère que nous avons maintenant deux nombres dans la bonne position finale :
4, 3, 5, 2, 0, 7, 9

Ensuite, nous répétons l’algorithme de tri, en ignorant ceux déjà triés, à la fin nous obtenons un tas :
⠀⠀0
⠀2⠀3
4 5 7 9

Ou sous forme de liste :
0, 2, 3, 4, 5, 7, 9

Mise en œuvre

L’algorithme est généralement divisé en trois fonctions :

Créer un tas
Algorithme de tamisage (heapify)
Remplacement du dernier élément non trié et du premier

Le tas est créé en parcourant l’avant-dernière ligne de l’arbre binaire à l’aide de la fonction heapify, de droite à gauche, jusqu’à la fin du tableau. Ensuite dans le cycle, le premier remplacement des nombres est effectué, après quoi le premier élément tombe/reste en place, à la suite de quoi le plus grand élément tombe à la première place, le cycle se répète avec une diminution du nombre de participants d’un, car après chaque passage, les nombres triés restent à la fin de la liste.

Exemple de tri par tas dans 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

Cet algorithme n’est pas facile à comprendre sans visualisation, donc la première chose que je recommande est d’écrire une fonction qui imprimera la vue actuelle de l’arbre binaire.