heapsort

Heapsort – classificação em pirâmide. Complexidade de tempo do algoritmo – O (n log n), rápido, certo? Eu chamaria isso de classificação de classificação de pedras que caem. Parece-me que a maneira mais fácil de explicar é visualmente.

A entrada é uma lista de números, por exemplo:
5, 0, 7, 2, 3, 9, 4

Da esquerda para a direita, uma estrutura de dados é criada – uma árvore binária, ou como eu chamo – pirâmide. Os elementos da pirâmide podem ter no máximo dois elementos filhos, mas apenas um elemento superior.

Vamos fazer uma árvore binária:
⠀⠀5
⠀0⠀7
2 3 9 4

Se você olhar a pirâmide por muito tempo, verá que são apenas números de uma matriz, vindo um após o outro, o número de elementos em cada andar é multiplicado por dois.

A seguir, a diversão começa; vamos classificar a pirâmide de baixo para cima usando o método das pedras caindo (heapify). A classificação poderia ser iniciada a partir do último andar (2 3 9 4), mas não adianta porque não há piso abaixo onde você possa cair.

Portanto, começamos a descartar elementos do penúltimo andar (0 7)
⠀⠀5
⠀0⠀7
2 3 9 4

O primeiro elemento a cair é selecionado da direita, no nosso caso é 7, então olhamos o que está abaixo dele, e abaixo dele estão 9 e 4, nove é maior que quatro, e também nove é maior que Sete! Colocamos 7 em 9 e colocamos 9 no lugar 7.
⠀⠀5
⠀0⠀9
2 3 7 4

A seguir, entendemos que o sete não tem onde cair, passamos para o número 0, que está localizado no penúltimo andar à esquerda:
⠀⠀5
⠀0⠀9
2 3 7 4

Vamos ver o que há por baixo – 2 e 3, dois é menor que três, três é maior que zero, então trocamos zero por três:
⠀⠀5
⠀3⠀9
2 0 7 4

Quando chegar ao final do andar, vá para o andar de cima e largue tudo lá, se puder.
O resultado é uma estrutura de dados – um heap, ou seja, max heap, porque no topo está o maior elemento:
⠀⠀9
⠀3⠀7
2 0 5 4

Se você retornar para uma representação de array, você obterá uma lista:
[9, 3, 7, 2, 0, 5, 4]

A partir disso podemos concluir que ao trocar o primeiro e o último elemento, obtemos o primeiro número na posição final ordenada, ou seja, 9 deve estar no final da lista ordenada, troque de lugar:
[4, 3, 7, 2, 0, 5, 9]

Vejamos uma árvore binária:
⠀⠀4
⠀3⠀7
2 0 5 9

O resultado é uma situação em que a parte inferior da árvore está ordenada, basta colocar 4 na posição correta, repetir o algoritmo, mas não levar em consideração os números já ordenados, nomeadamente 9:
⠀⠀4
⠀3⠀7
2 0 5 9

⠀⠀7
⠀3⠀4
2 0 5 9

⠀⠀7
⠀3⠀5
2 0 4 9

Acontece que nós, tendo perdido 4, aumentamos o próximo maior número depois de 9 – 7. Troque o último número não classificado (4) e o maior número (7)
⠀⠀4
⠀3⠀5
2 0 7 9

Acontece que agora temos dois números na posição final correta:
4, 3, 5, 2, 0, 7, 9

Em seguida repetimos o algoritmo de classificação, ignorando os já classificados, no final obtemos um heap tipo:
⠀⠀0
⠀2⠀3
4 5 7 9

Ou como uma lista:
0, 2, 3, 4, 5, 7, 9

Implementação

O algoritmo geralmente é dividido em três funções:

Criando uma pilha
Algoritmo de peneiração (heapify)
Substituindo o último elemento não classificado e o primeiro

O heap é criado percorrendo a penúltima linha da árvore binária usando a função heapify, da direita para a esquerda, até o final do array. A seguir no ciclo, é feita a primeira substituição de números, após a qual o primeiro elemento cai/permanece no lugar, como resultado o elemento maior cai em primeiro lugar, o ciclo é repetido com uma diminuição de participantes em um, porque após cada passagem, os números classificados permanecem no final da lista.

Exemplo de Heapsort em 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

Esse algoritmo não é fácil de entender sem visualização, então a primeira coisa que recomendo é escrever uma função que imprima a visualização atual da árvore binária.