Please enable JavaScript.

Coggle requires JavaScript to display documents.

Heap and Heapsort - Coggle Diagram

- - - - Primeiro, o algoritmo constrói um heap a partir do array de entrada. Isso pode ser feito usando o método de construção bottom-up, que tem uma eficiência de O(n)
        
        etapa 2
        
        Remoções Sucessivas do Máximo
        
        aplica a operação de remoção da raiz n-1 vezes
        
        Em cada iteração, o maior elemento (que está na raiz do heap) é removido e colocado no final do array, na posição que fica vaga. A parte do array que representa o heap diminui em um elemento
        
        Como a remoção da raiz em um heap de tamanho k leva tempo O(log k), e essa operação é repetida n-1 vezes, a eficiência desta etapa é O(n log n)
  - - - Somando as duas etapas, a eficiência total do Heapsort é Θ(n log n), tanto no pior caso quanto no caso médio
    - - É um algoritmo in-place, ou seja, não requer armazenamento extra significativo, o que é uma grande vantagem sobre o Mergesort
    - - Em testes com arquivos aleatórios, o Heapsort geralmente é mais lento que o Quicksort, mas pode ser competitivo com o Mergesort