Heapsort: complexidade de melhor e pior caso
Gabarito: letra D. O Heapsort, independentemente da ordem dos elementos, executa as fases de construção da heap (BUILD-MAX-HEAP, O(n)) e de extração sucessiva do máximo (n vezes MAX-HEAPIFY, cada O(log n)), resultando em O(n log n) tanto para o melhor quanto para o pior caso. Não há variação significativa pela entrada, diferentemente do Quicksort.
A banca testa o conhecimento da complexidade assintótica do Heapsort, que é invariante.
Alternativa A — ❌ Incorreta
Afirma melhor caso O(1) e pior O(n log n). O(1) só seria possível se a ordenação já estivesse pronta e não houvesse trabalho algum, mas o Heapsort sempre percorre todos os elementos para construir a heap, independentemente de já estarem ordenados.
Alternativa B — ❌ Incorreta
Propõe O(n²) e O(n⁴), complexidades muito superiores às reais. O Heapsort nunca atinge ordem quadrática.
Alternativa C — ❌ Incorreta
Apresenta O(n) e O(n²). A construção da heap é O(n), mas a ordenação completa (n extrações) é O(n log n); o melhor caso não é O(n) pois mesmo que os dados já estejam em heap, o algoritmo ainda precisa extrair todos os elementos e reconstruir a heap.
Alternativa D — ✅ Correta ⟵ GABARITO
Exata: O(n log n) para melhor e pior caso. O texto de apoio do CLRS confirma: "o tempo de execução da ordenação por heap é O(n lg n)".
CLRS (Introdução aos Algoritmos):
"o tempo de execução da ordenação por heap é O(n lg n)" (Capítulo 6).
Alternativa E — ❌ Incorreta
Embora O(n log n⁴) seja matematicamente equivalente a O(n log n) (pois log n⁴ = 4 log n, constante), a notação com o expoente 4 sobre o log é atípica e a banca a considerou incorreta. Além disso, o pior caso do Heapsort é O(n log n), não O(n log n⁴) — a forma correta é sem o expoente. Normalmente, a expressão n log n é padrão.
Gabarito: letra D — o Heapsort tem complexidade O(n log n) para todos os casos.