- Como é realizada e qual a importância da operação de amontoa?
Passo 1
O enunciado pergunta duas coisas claras: (1) “Como é realizada a operação de amontoa?” e (2) “Qual a importância da operação de amontoa?”.
Não são dados valores numéricos nem uma figura — só é pedido explicar o procedimento e justificar sua utilidade. Vou explicar passo a passo o que é preciso saber para entender e executar a operação e por que ela é importante.
Não são dados valores numéricos nem uma figura — só é pedido explicar o procedimento e justificar sua utilidade. Vou explicar passo a passo o que é preciso saber para entender e executar a operação e por que ela é importante.
Passo 2
O que precisa ficar cristalino antes de executar a amontoa: o que é um heap e como representá‑lo em array. Vou ensinar isso devagarinho.
- Definição: um heap (vamos falar de max‑heap para fixar uma ideia) é uma estrutura onde cada nó tem valor maior ou igual aos valores dos seus filhos. Em símbolos: para todo nó
que tem filhos, vale . - Representação em array: um heap binário completo pode ser guardado em um vetor
de elementos com índices . As fórmulas de índice são: Essas fórmulas são essenciais — memorize-as ou decore com carinho. - Observação prática: nós que não têm filhos são as folhas. Em um array de tamanho
, o último nó que pode ter filho é . É por isso que começamos a amontoar a partir daí (vou detalhar adiante).
Passo 3
A operação básica usada dentro da amontoa chama‑se “sift‑down” (ou “afundar” / “restaurar heap para baixo”). Vou descrever passo a passo o procedimento e por que ele funciona.
Objetivo do sift‑down em um nó
: garantir que a subárvore com raiz em
satisfaça a propriedade de max‑heap, assumindo que as subárvores das crianças já são heaps.
Algoritmo (em palavras):
- Compare
com seus filhos e (quando existirem). - Se
for maior ou igual aos dois filhos (ou se não tiver filhos), a subárvore já é heap — pare. - Caso contrário, troque
com o maior dos dois filhos (para max‑heap). Agora o valor antigo de está descendo para uma posição de índice maior. - Atualize
para o índice onde o valor foi trocado (filho escolhido) e repita desde o passo 1 até estabilizar.
Importante: todo swap diminui o índice relativo ao nível do heap (o valor “desce”), então o processo termina quando atinge uma folha. Esse procedimento custa tempo proporcional à altura da subárvore (no pior caso
).
Passo 4
Como montar um heap inteiro (a operação “amontoa” propriamente dita). Vamos ao algoritmo clássico, que é usado em Heapsort e em construção de filas de prioridade.
Algoritmo build‑heap (amontoa), em palavras:
- Dado um array
de tamanho , percorra os índices de até (decrescendo). - Para cada
, execute o procedimento sift‑down na posição .
Por que começamos em
? Porque índices maiores são folhas (não têm filhos) e folhas já satisfazem a propriedade de heap sozinhas; não faz sentido tentar “afundar” uma folha. Assim, começamos no último nó interno e subimos até a raiz, garantindo que a cada passo as subárvores abaixo já são heaps.
Pseudocódigo enxuto (escrito em palavras para a prova):
- Para
de até : - executar sift‑down em
.
- executar sift‑down em
Passo 5
Exemplo prático passo a passo — isso ajuda muito para entender e para a prova. Suponha o array inicial
Aqui
. Calculamos
. Então começamos em
, depois
, depois
.
- i = 2:
. Filhos: índices e (o não existe). . Já temos , nada a fazer.
Estado:. - i = 1:
. Filhos: , . Maior filho é em índice . Como , trocamos com .
Após swap:.
Agoravira . Índice tem filhos fora do limite (são folhas), processo termina. - i = 0:
. Filhos: , . Maior filho é em índice . Como , trocamos com .
Após swap:.
Agoravira . Filhos de são índices e ; existe, não. Como , trocamos com .
Após swap final:.
Agora o array representa um max‑heap: cada pai é maior ou igual aos filhos.
Esse exemplo mostra como a amontoa transforma um array qualquer num heap em alguns swaps locais usando sift‑down.
Passo 6
Complexidade: por que a construção inteira custa
e não
? Vamos entender de forma intuitiva e com um cálculo simples.
- Observação ingênua: cada sift‑down custa no pior caso a altura do heap
, e fazemos isso em cerca de nós; isso sugeriria . Mas muitos nós estão bem perto das folhas e têm altura pequena; apenas poucos nós perto da raiz têm altura grande. - Prova intuitiva (conta por níveis): em um heap de
nós, o número de nós no nível com altura é no máximo . Cada um desses nós custa no máximo para afundar. Então o custo total satisfaz (com constantes) A soma converge e vale uma constante (na verdade , se ajustar índices, ou em outra forma vale dependendo da convenção). Portanto . - Resultado prático: a construção bottom‑up é linear,
. Isso é muito útil — é melhor do que inserir um a um elementos em uma fila de prioridade (cada inserção custando levaria ).
Se quiser um número: a análise mais detalhada mostra que o número de comparações fica próximo de
na construção, o que é linear.
Passo 7
Importância da operação “amontoa” (uso prático — o que cai na prova e o que importa na engenharia):
- Heapsort: para ordenar um array com Heapsort você primeiro executa amontoa (build‑heap) em
e depois repete vezes: troca raiz com último, reduz o tamanho e sift‑down na raiz ( cada). Resultado: Heapsort tem custo no total e usa memória constante. A amontoa é a etapa que permite esse algoritmo. - Filas de prioridade (priority queue): se você precisa responder repetidas operações extract‑max e decrease/increase‑key, construir o heap em
quando os dados chegam é muito mais eficiente do que inserir um a um. - Na prática: amontoa é a forma rápida de transformar dados “bagunçados” em uma estrutura que dá acesso rápido ao maior (ou menor) elemento em
e permite remoções em . - Em provas: é comum pedirem a execução manual da amontoa em um array pequeno (como fiz no exemplo) ou pedir para justificar a complexidade
. Memorize a técnica bottom‑up e o argumento por níveis — isso resolve ambos.
Passo 8
Dicas rápidas para a prova (práticas e que salvam tempo):
- Sempre desenhe o array e marque índices. Lembre que filhos são
e . - Comece o build‑heap em
e ande para trás até . - Ao fazer sift‑down, escolha o maior (para max‑heap) entre filhos antes de trocar; isso evita erros.
- Para justificar a complexidade, use a ideia de “muitos nós estão perto das folhas” e a soma em potências de
que converge; escreva isso curto na prova. - Treine com arrays de tamanho
a para pegar o jeito dos swaps — na hora da prova você vai voar e ficar mais calmo.
Passo 9
Recapitulando em linguagem bem direta: a amontoa transforma um array em um heap usando operações locais de “afundar” (sift‑down) começando dos últimos nós internos até a raiz; isso custa tempo linear
e é a peça central de Heapsort e da construção eficiente de filas de prioridade.
Resposta
Como é realizada: a operação de amontoa (build‑heap) percorre os índices de
até
e, para cada índice
, aplica o procedimento sift‑down (comparar com filhos
,
e trocar com o maior filh o quando necessário) até que a subárvore com raiz em
satisfaça a propriedade de heap.
Qual a importância: amontoa transforma um array arbitrário em um heap em tempo linear
; é fundamental para Heapsort (etapa inicial) e para construir eficientemente filas de prioridade, oferecendo uma base rápida para operações subsequentes de remoção/extração em
.