Este conteúdo apresenta o Heap Sort, explicando a estrutura de heap (árvore binária completa), a representação em vetor, a construção do heap, o processo de heapify e os passos da ordenação com heap máximo.
Heap Sort utiliza um heap máximo para extrair o maior elemento repetidamente, trocando com o final do vetor e re-ordenando o heap até ordenar tudo.
O Heap Sort utiliza uma árvore binária completa com propriedade de heap para extrair o maior elemento. Qual afirmação descreve corretamente o papel da raiz em um heap máximo?
Resposta correta: C) A raiz é o maior elemento do heap.
Justificativa: Em um heap máximo, a raiz representa o maior elemento do conjunto ordenado pelo heap.
Após trocar a raiz pelo último elemento, qual é o procedimento que restaura a propriedade do heap na raiz?
Resposta correta: B) Heapify (rearranjar)
Justificativa: heapify reorganiza a subárvore para que a raiz seja o maior elemento entre a raiz e seus filhos, preservando a propriedade do heap.
Qual o índice inicial para aplicar heapify ao construir um heap máximo a partir de um vetor com n elementos?
Resposta correta: C) ⌊n/2⌋ - 1
Justificativa: Os nós não folhados são aqueles com índice menor que ⌊n/2⌋; começamos de ⌊n/2⌋ - 1 para heapify descendente.
Considere as operações de construção do heap + o processo de ordenação. Qual é a complexidade de tempo no pior caso e o espaço extra utilizado?
Resposta correta: A) O(n log n) tempo e O(1) espaço extra
Justificativa: HeapSort tem tempo ótimo O(n log n) no pior caso e usa apenas espaço constante além do vetor de entrada.