Marcos de Castro
31/12/1969 • 21:00
Gabarito: a) O heapsort é um algoritmo de ordenação que utiliza uma estrutura de dados chamada heap para ordenar os elementos. A característica principal do heapsort é que ele realiza a ordenação in-place, ou seja, não necessita de espaço adicional proporcional ao tamanho do vetor de entrada.
Durante a execução do heapsort, a quantidade de memória extra utilizada é constante, pois o algoritmo manipula o arranjo original para construir o heap e extrair os elementos ordenados, sem alocar estruturas auxiliares de tamanho variável.
Portanto, a afirmação de que a quantidade de elementos armazenada fora do arranjo de entrada é constante está correta, pois o heapsort é um algoritmo eficiente em termos de uso de memória, utilizando espaço extra O(1).
Para reforçar, o heapsort tem complexidade de tempo O(n log n) e complexidade de espaço O(1), o que o torna um algoritmo de ordenação estável em termos de uso de memória, diferente de outros algoritmos como o mergesort, que requerem espaço adicional proporcional ao tamanho da entrada.
Durante a execução do heapsort, a quantidade de memória extra utilizada é constante, pois o algoritmo manipula o arranjo original para construir o heap e extrair os elementos ordenados, sem alocar estruturas auxiliares de tamanho variável.
Portanto, a afirmação de que a quantidade de elementos armazenada fora do arranjo de entrada é constante está correta, pois o heapsort é um algoritmo eficiente em termos de uso de memória, utilizando espaço extra O(1).
Para reforçar, o heapsort tem complexidade de tempo O(n log n) e complexidade de espaço O(1), o que o torna um algoritmo de ordenação estável em termos de uso de memória, diferente de outros algoritmos como o mergesort, que requerem espaço adicional proporcional ao tamanho da entrada.