Heapsort é um algoritmo de ordenação baseado na estrutura de dados heap. Sobre as características desse algoritmo de ordenação, assinale, a afirmativa correta.

Gabarito

B

Comentário do professor

Heapsort tem tempo de execução no pior caso \(O(n \log n)\). Essa afirmação decorre da estrutura e das operações fundamentais do algoritmo.

Primeiro, constrói-se um heap a partir do vetor de entrada; esse passo (heapify) pode ser feito em \(O(n)\) usando o processo bottom-up.

Em seguida, realiza-se repetidamente a operação de extract-max (ou extract-min), removendo a raiz e restaurando a propriedade de heap com o procedimento de sift-down, que percorre a altura da árvore.

Como a altura do heap é \(O(\log n)\) e essa restauração ocorre \(n\) vezes, essa fase custa \(O(n \log n)\).

Somando as fases: \(O(n) + O(n \log n) = O(n \log n)\), que é o comportamento no pior caso.