- 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
de tamanho
, para todo índice
que tenha filhos, deve valer
Se
está ordenado em ordem decrescente, então para quaisquer
temos
. Como
e
, automaticamente
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
elementos em ordem decrescente é tipicamente
. Em contrapartida, o algoritmo padrão BUILD-MAX-HEAP, que aplica MAX-HEAPIFY de baixo para cima, executa em
. 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
, enquanto o algoritmo de construção de heap padrão custa
. Logo, a ideia funciona, mas é ineficiente.