A seguinte figura apresenta um algoritmo de ordenação da tabela L, de n elementos, segundo o seu campo chave. Assinale a alternativa que descreve o método de ordenação.

Gabarito

D

Comentário do professor

O Heapsort ordena transformando o vetor em um heap máximo e extraindo repetidamente o maior elemento. Após construir o heap, o maior fica na raiz; troca‑se a raiz com o último elemento, reduz‑se o tamanho do heap e aplica‑se heapify na raiz para restaurar a propriedade de heap.

Os passos principais são: construir o heap a partir do array; para k = n down to 2, trocar A[1] com A[k], decrementar k e executar sift‑down (heapify) na raiz.

Num array com índice zero, os filhos de i são \(2i+1\) e \(2i+2\). A construção do heap leva \(O(n)\), cada remoção custa \(O(\log n)\), portanto o custo total é \(O(n\log n)\).

É um algoritmo in‑place (uso extra de memória constante) e não estável, indicado quando se quer tempo garantido \(O(n\log n)\) sem memória adicional.