1. Critique a seguinte ideia: para transformar um vetor arbitrário em max-heap, basta colocá-lo em ordem decrescente.

Passo 1

O enunciado pede para criticar a ideia “para transformar um vetor arbitrário em max-heap, basta colocá-lo em ordem decrescente”. O tema envolvido é a estrutura de dados heap, em especial a construção de um max-heap, e a análise de complexidade dos métodos de construção.

Passo 2

Num max-heap representado em vetor A de tamanho n, para todo índice i que tenha filhos, deve valer
A[i] \ge A[2i] \quad\text{e}\quad A[i] \ge A[2i+1].
Se A está ordenado em ordem decrescente, então para quaisquer i<j temos A[i]\ge A[j]. Como 2i>i e 2i+1>i, automaticamente
A[i]\ge A[2i]\quad\text{e}\quad A[i]\ge A[2i+1],
logo o vetor ordenado decrescentemente satisfaz a propriedade de max-heap.

Passo 3

Apesar de ser correto produzir um max-heap via ordenação, a complexidade de ordenar n elementos em ordem decrescente é tipicamente \mathcal O(n\log n). Em contrapartida, o algoritmo padrão BUILD-MAX-HEAP, que aplica MAX-HEAPIFY de baixo para cima, executa em \mathcal O(n). Portanto usar ordenação é assintoticamente mais caro que a construção direta de heap.

Passo 4

Além do maior custo de tempo, a ordenação global impõe restrições desnecessárias — em heap só importam comparações locais entre pais e filhos. Em cenários de desempenho crítico, “sort + heap” é subótimo comparado a BUILD-MAX-HEAP.

Resposta

Embora ordenar em ordem decrescente gere um vetor que satisfaz a propriedade de max-heap, essa estratégia custa \mathcal O(n\log n), enquanto o algoritmo de construção de heap padrão custa \mathcal O(n). Logo, a ideia funciona, mas é ineficiente.

Exercícios relacionados