1. 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.

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ó i que tem filhos, vale A[i]\ge A[\text{filho}].
  • Representação em array: um heap binário completo pode ser guardado em um vetor A de n elementos com índices 0,1,\dots,n-1. As fórmulas de índice são: \text{filho\_esq}(i)=2i+1,\qquad \text{filho\_dir}(i)=2i+2,\qquad \text{pai}(i)=\left\lfloor\frac{i-1}{2}\right\rfloor.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 n, o último nó que pode ter filho é \left\lfloor\frac{n}{2}\right\rfloor-1. É 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ó i: garantir que a subárvore com raiz em i satisfaça a propriedade de max‑heap, assumindo que as subárvores das crianças já são heaps.
Algoritmo (em palavras):
  1. Compare A[i] com seus filhos A[2i+1] e A[2i+2] (quando existirem).
  2. Se A[i] for maior ou igual aos dois filhos (ou se não tiver filhos), a subárvore já é heap — pare.
  3. Caso contrário, troque A[i] com o maior dos dois filhos (para max‑heap). Agora o valor antigo de A[i] está descendo para uma posição de índice maior.
  4. Atualize i 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 \mathcal{O}(\log n)).

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:
  1. Dado um array A de tamanho n, percorra os índices i de \left\lfloor\frac{n}{2}\right\rfloor-1 até 0 (decrescendo).
  2. Para cada i, execute o procedimento sift‑down na posição i.
Por que começamos em \left\lfloor\frac{n}{2}\right\rfloor-1? 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 i de \left\lfloor\frac{n}{2}\right\rfloor-1 até 0:
    • executar sift‑down em i.

Passo 5

Exemplo prático passo a passo — isso ajuda muito para entender e para a prova. Suponha o array inicial
A=[3,\,1,\,6,\,5,\,2,\,4].
Aqui n=6. Calculamos \left\lfloor\frac{n}{2}\right\rfloor-1=\left\lfloor 3\right\rfloor-1=2-1=2. Então começamos em i=2, depois i=1, depois i=0.
  • i = 2: A[2]=6. Filhos: índices 5 e 6 (o 6 não existe). A[5]=4. Já temos 6\ge4, nada a fazer.
    Estado: [3,1,6,5,2,4].
  • i = 1: A[1]=1. Filhos: A[3]=5, A[4]=2. Maior filho é 5 em índice 3. Como 1<5, trocamos A[1] com A[3].
    Após swap: [3,5,6,1,2,4].
    Agora i vira 3. Índice 3 tem filhos fora do limite (são folhas), processo termina.
  • i = 0: A[0]=3. Filhos: A[1]=5, A[2]=6. Maior filho é 6 em índice 2. Como 3<6, trocamos A[0] com A[2].
    Após swap: [6,5,3,1,2,4].
    Agora i vira 2. Filhos de 2 são índices 5 e 6; A[5]=4 existe, A[6] não. Como 3<4, trocamos A[2] com A[5].
    Após swap final: [6,5,4,1,2,3].
    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 \mathcal{O}(n) e não \mathcal{O}(n\log n)? 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 \approx \log n, e fazemos isso em cerca de n nós; isso sugeriria \mathcal{O}(n\log n). 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 nós, o número de nós no nível com altura h é no máximo \left\lceil\frac{n}{2^{h+1}}\right\rceil. Cada um desses nós custa no máximo h para afundar. Então o custo total T(n) satisfaz (com constantes) T(n)\le \sum_{h=0}^{\lfloor\log n\rfloor} \frac{n}{2^{h+1}}\cdot h = n\sum_{h\ge0}\frac{h}{2^{h+1}}.A soma \sum_{h\ge0}\frac{h}{2^{h+1}} converge e vale uma constante (na verdade 1, se ajustar índices, ou em outra forma vale 2 dependendo da convenção). Portanto T(n)=\mathcal{O}(n).
  • Resultado prático: a construção bottom‑up é linear, T(n)=\mathcal{O}(n). Isso é muito útil — é melhor do que inserir um a um n elementos em uma fila de prioridade (cada inserção custando \mathcal{O}(\log n) levaria \mathcal{O}(n\log n)).
Se quiser um número: a análise mais detalhada mostra que o número de comparações fica próximo de 2n 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 \mathcal{O}(n) e depois repete n-1 vezes: troca raiz com último, reduz o tamanho e sift‑down na raiz ( \mathcal{O}(\log n) cada). Resultado: Heapsort tem custo \mathcal{O}(n\log n) 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 \mathcal{O}(n) 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 \mathcal{O}(1) e permite remoções em \mathcal{O}(\log n).
  • Em provas: é comum pedirem a execução manual da amontoa em um array pequeno (como fiz no exemplo) ou pedir para justificar a complexidade \mathcal{O}(n). 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 2i+1 e 2i+2.
  • Comece o build‑heap em \left\lfloor\frac{n}{2}\right\rfloor-1 e ande para trás até 0.
  • 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 1/2 que converge; escreva isso curto na prova.
  • Treine com arrays de tamanho 6 a 10 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 \mathcal{O}(n) 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 \left\lfloor\frac{n}{2}\right\rfloor-1 até 0 e, para cada índice i, aplica o procedimento sift‑down (comparar com filhos 2i+1, 2i+2 e trocar com o maior filh o quando necessário) até que a subárvore com raiz em i satisfaça a propriedade de heap.
Qual a importância: amontoa transforma um array arbitrário em um heap em tempo linear \mathcal{O}(n); é 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 \mathcal{O}(\log n).

Exercícios relacionados