Uma fila de prioridade é uma estrutura que sempre entrega o elemento de maior (ou menor) prioridade, independentemente da ordem de inserção. Não basta uma fila comum nem um vetor ordenado: precisamos de algo que insira e remova o máximo em O(log n). A estrutura ideal para isso é o heap — uma árvore binária completa armazenada como vetor, com uma propriedade de ordenação parcial que garante acesso ao máximo em O(1) e operações de atualização em O(log n).

1. O que é um Heap

Um max-heap é uma árvore binária que satisfaz duas propriedades simultaneamente:

1. Propriedade estrutural: a árvore é completa — todos os níveis estão preenchidos, exceto possivelmente o último, que é preenchido da esquerda para a direita.
2. Propriedade do heap (max): o valor de cada nó é maior ou igual ao valor de seus filhos. Em particular, a raiz sempre contém o maior elemento.

Um min-heap é simétrico: cada nó é menor ou igual a seus filhos, e a raiz sempre contém o menor elemento.

Exemplo de max-heap válido:

                 90
              /       \
           75           80
          /   \        /   \
        55     60    70     40
       /  \   /
      20  30 45

Verificação da propriedade:
  90 ≥ 75, 80  ✓
  75 ≥ 55, 60  ✓
  80 ≥ 70, 40  ✓
  55 ≥ 20, 30  ✓
  60 ≥ 45      ✓

2. Representação em vetor

A propriedade estrutural (árvore completa) permite armazenar o heap em um vetor sem nenhum ponteiro. A correspondência entre posições do vetor e nós da árvore segue as fórmulas abaixo (índices começando em 0):

Exemplo — mesmo heap do item anterior:

Árvore:                        Vetor (índice base 0):

             90 [0]             [0]  [1]  [2]  [3]  [4]  [5]  [6]  [7]  [8]  [9]
          /        \            90   75   80   55   60   70   40   20   30   45
       75 [1]      80 [2]
      /    \      /    \       Relações:
   55[3]  60[4] 70[5] 40[6]     pai(1) = (1-1)/2 = 0  → 90  ✓  (75 < 90)
   /  \   /                     pai(9) = (9-1)/2 = 4  → 60  ✓  (45 < 60)
 20[7] 30[8] 45[9]              filho_esq(2) = 2×2+1 = 5  → 70  ✓
                                filho_dir(2) = 2×2+2 = 6  → 40  ✓

3. Operação central: heapify (corrigir descendo)

O heapify (também chamado de sift-down ou descer) é a operação que restaura a propriedade do heap em um nó que pode estar menor do que um de seus filhos. Ela é usada na remoção e na construção do heap.

Algoritmo:

1. Compare o nó i com seus filhos esquerdo e direito.
2. Se o maior filho for maior que o nó, troque e repita a partir da nova posição.
3. Pare quando o nó for maior ou igual a ambos os filhos, ou quando não houver mais filhos.

/* heapify: restaura a propriedade do max-heap descendo o nó i.
   a[] = vetor do heap, n = número de elementos ativos, i = nó a descer. */
void heapify(int a[], int n, int i) {
    int maior = i;
    int esq   = 2*i + 1;
    int dir   = 2*i + 2;

    if (esq < n && a[esq] > a[maior]) maior = esq;
    if (dir < n && a[dir] > a[maior]) maior = dir;

    if (maior != i) {
        int tmp = a[i]; a[i] = a[maior]; a[maior] = tmp;
        heapify(a, n, maior);
    }
}

Exemplo de heapify:

Heap com nó raiz inválido (5 no lugar de 90):

             5 [0]   ← problema!
          /        \
       75 [1]      80 [2]
      /    \      /    \
   55[3]  60[4] 70[5] 40[6]

heapify(a, 7, 0):
  Passo 1: nó=5, esq=75, dir=80. Maior filho: 80[2]. 5 < 80 → troca.
             80
          /      \
        75         5    ← 5 desceu
       /  \       / \
     55   60    70  40

  Passo 2: nó=5 em [2], esq=70[5], dir=40[6]. Maior filho: 70[5]. 5 < 70 → troca.
             80
          /      \
        75         70
       /  \       /  \
     55   60    5    40   ← 5 chegou ao final (folha)

  Passo 3: nó=5 em [5], esq=11(fora), dir=12(fora). Sem filhos. Para.

Resultado: [80, 75, 70, 55, 60, 5, 40]  ← heap válido.

O heapify percorre no máximo a altura da árvore: O(log n).

4. Operação: sift-up (corrigir subindo)

O sift-up restaura a propriedade do heap em um nó que pode estar maior do que seu pai. Ele é usado na inserção.

Algoritmo:

1. Compare o nó i com seu pai.
2. Se o nó for maior que o pai, troque e repita a partir do pai.
3. Pare quando chegar na raiz ou quando o pai for maior ou igual.

/* sift-up: restaura a propriedade do max-heap subindo o nó i. */
void siftUp(int a[], int i) {
    while (i > 0) {
        int pai = (i - 1) / 2;
        if (a[i] > a[pai]) {
            int tmp = a[i]; a[i] = a[pai]; a[pai] = tmp;
            i = pai;
        } else {
            break;
        }
    }
}

Exemplo de sift-up:

Heap com novo elemento 85 inserido no final (posição [10]):

                   90 [0]
               /           \
           75 [1]           80 [2]
          /     \           /    \
       55 [3]  60 [4]   70 [5]  40 [6]
       /  \    /
    20[7] 30[8] 45[9]  85[10]  ← novo, posição [10]

siftUp(a, 10):
  Passo 1: i=10, pai=(10-1)/2=4 → valor 60. 85 > 60 → troca.

                   90
               /           \
           75               80
          /     \           /    \
       55       85       70      40
       /  \    /
    20    30  45  60  ← 85 subiu, 60 desceu

  Passo 2: i=4, pai=(4-1)/2=1 → valor 75. 85 > 75 → troca.

                   90
               /           \
           85               80
          /     \           /    \
       55       75       70      40
       /  \    /
    20    30  45  60  ← 85 subiu, 75 desceu

  Passo 3: i=1, pai=(1-1)/2=0 → valor 90. 85 < 90 → para.

Resultado: [90, 85, 80, 55, 75, 70, 40, 20, 30, 45, 60]  ← heap válido.

O sift-up percorre no máximo a altura da árvore: O(log n).

5. Inserção

Para inserir um novo elemento no heap:

1. Adicione o elemento no final do vetor (próxima posição livre).
2. Execute o sift-up a partir dessa posição.

Exemplo — inserir 85 no heap [90, 75, 80, 55, 60, 70, 40, 20, 30, 45]:

Após adicionar 85 na posição [10]:
[90, 75, 80, 55, 60, 70, 40, 20, 30, 45, 85]

85 está em [10]. Pai: (10-1)/2 = 4 → valor 60. 85 > 60 → troca.
[90, 75, 80, 55, 85, 70, 40, 20, 30, 45, 60]

85 agora em [4]. Pai: (4-1)/2 = 1 → valor 75. 85 > 75 → troca.
[90, 85, 80, 55, 75, 70, 40, 20, 30, 45, 60]

85 agora em [1]. Pai: (1-1)/2 = 0 → valor 90. 85 < 90 → para.

Resultado: [90, 85, 80, 55, 75, 70, 40, 20, 30, 45, 60]

Árvore resultante:
                 90
              /       \
           85           80
          /   \        /   \
        55     75    70     40
       /  \   /  \
      20  30 45  60

Heap válido: 85 subiu dois níveis até a posição correta.

Custo: O(log n) — no máximo a altura da árvore.

6. Remoção do máximo

Remover a raiz (maior elemento) de um heap de forma direta não é viável, pois deixaria dois filhos sem pai. A estratégia correta é:

1. Guarde o valor da raiz (esse é o máximo que será retornado).
2. Mova o último elemento do vetor para a raiz.
3. Reduza o tamanho do heap em 1.
4. Execute o heapify a partir da raiz.

Exemplo — remover o máximo de [90, 75, 80, 55, 60, 70, 40, 20, 30, 45]:

Retorna 90. Move 45 (último) para a raiz. Tamanho = 9.
[45, 75, 80, 55, 60, 70, 40, 20, 30]

heapify a partir de [0]:
  45 vs 75[1] e 80[2]. Maior: 80. 45 < 80 → troca.
  [80, 75, 45, 55, 60, 70, 40, 20, 30]

  45 em [2] vs 70[5] e 40[6]. Maior: 70. 45 < 70 → troca.
  [80, 75, 70, 55, 60, 45, 40, 20, 30]

  45 em [5]: filhos seriam [11] e [12], fora do heap. Para.

Resultado: [80, 75, 70, 55, 60, 45, 40, 20, 30]

Árvore resultante:
                 80
              /       \
           75           70
          /   \        /   \
        55     60    45     40
       /  \
      20   30

Custo: O(log n). Acessar o máximo sem remover (peek) é O(1): basta ler a[0].

7. Construção do heap em O(n) — build-heap

Dado um vetor arbitrário, é possível transformá-lo em heap em tempo linear usando o método bottom-up: começar pelos nós internos mais profundos e aplicar heapify em cada um, subindo até a raiz. Folhas não precisam de heapify (já são heaps trivialmente).

O último nó interno tem índice n/2 − 1. O loop vai de n/2−1 até 0.

/* Constrói o heap no próprio vetor em O(n). */
void buildHeap(int a[], int n) {
    for (int i = n/2 - 1; i >= 0; i--)
        heapify(a, n, i);
}

Exemplo — build-heap em [5, 3, 8, 4, 1, 7, 2]:

Vetor inicial: [5, 3, 8, 4, 1, 7, 2]    (n=7, último interno: 7/2-1 = 2)

Árvore inicial:
          5 [0]
        /       \
      3 [1]     8 [2]
     /   \     /   \
   4[3]  1[4] 7[5] 2[6]

─── i=2: heapify em 8[2] ───
  Filhos: 7[5] e 2[6]. 8 > 7 e 8 > 2. Sem troca.
  [5, 3, 8, 4, 1, 7, 2]

─── i=1: heapify em 3[1] ───
  Filhos: 4[3] e 1[4]. Maior: 4[3]. 3 < 4 → troca.
  [5, 4, 8, 3, 1, 7, 2]
  Novo nó 3 em [3]: filhos seriam [7] e [8], fora do heap. Para.

─── i=0: heapify em 5[0] ───
  Filhos: 4[1] e 8[2]. Maior: 8[2]. 5 < 8 → troca.
  [8, 4, 5, 3, 1, 7, 2]
  Novo nó 5 em [2]: filhos: 7[5] e 2[6]. Maior: 7[5]. 5 < 7 → troca.
  [8, 4, 7, 3, 1, 5, 2]
  Novo nó 5 em [5]: sem filhos. Para.

Resultado: [8, 4, 7, 3, 1, 5, 2]

Árvore resultante (heap válido):
          8
        /   \
       4     7
      / \   / \
     3   1 5   2

8. Fila de Prioridade

Uma fila de prioridade é um TAD que suporta três operações:

Uma implementação simples em C usando vetor estático:

#define CAP 1024

typedef struct {
    int dados[CAP];
    int tam;
} FilaPrioridade;

void fpInserir(FilaPrioridade *fp, int valor) {
    fp->dados[fp->tam] = valor;
    siftUp(fp->dados, fp->tam);
    fp->tam++;
}

int fpMaximo(FilaPrioridade *fp) {
    return fp->dados[0];   /* O(1) */
}

int fpRemoverMaximo(FilaPrioridade *fp) {
    int max    = fp->dados[0];
    fp->tam--;
    fp->dados[0] = fp->dados[fp->tam];
    heapify(fp->dados, fp->tam, 0);
    return max;
}

Aplicações clássicas de filas de prioridade:

• Agendamento de processos — o SO sempre executa o processo de maior prioridade.
• Algoritmo de Dijkstra — a cada passo, escolhe o vértice com menor distância acumulada.
• Compressão Huffman — sempre combina os dois símbolos de menor frequência.
• Simulação de eventos — os eventos são processados em ordem cronológica (min-heap de tempo).

9. Heap Sort

O Heap Sort usa o heap para ordenar um vetor in-place (sem alocação extra além de O(1)) em O(n log n) no pior caso. O algoritmo tem duas fases:

1. Fase 1 — build-heap: transforma o vetor em um max-heap. Custo: O(n).
2. Fase 2 — extração repetida: n−1 vezes, troca a raiz (máximo) com o último elemento do heap ativo, reduz o heap em 1 e aplica heapify. Custo: O(n log n).

Ao final, o vetor está ordenado em ordem crescente (usando max-heap).

void heapSort(int a[], int n) {
    buildHeap(a, n);                  /* fase 1: O(n)       */
    for (int i = n-1; i > 0; i--) {  /* fase 2: O(n log n) */
        int tmp = a[0]; a[0] = a[i]; a[i] = tmp;   /* máximo vai para o fim */
        heapify(a, i, 0);            /* reequilibra com heap de tamanho i */
    }
}

Exemplo completo — ordenar [5, 3, 8, 4, 1, 7, 2]:

══════════ FASE 1: build-heap ══════════

Entrada:  [5, 3, 8, 4, 1, 7, 2]
Resultado:[8, 4, 7, 3, 1, 5, 2]   ← max-heap (ver seção 7 para o passo-a-passo)

══════════ FASE 2: extrações ══════════

(heap ativo | já ordenado)

i=6: troca a[0]=8 com a[6]=2  →  [2, 4, 7, 3, 1, 5 | 8]
     heapify(n=6, i=0):
       2 vs 4,7 → troca com 7 → [7, 4, 2, 3, 1, 5 | 8]
       2 em [2] vs 5[5] → troca → [7, 4, 5, 3, 1, 2 | 8]
       2 em [5]: sem filhos. Para.
     Heap: [7, 4, 5, 3, 1, 2]

i=5: troca a[0]=7 com a[5]=2  →  [2, 4, 5, 3, 1 | 7, 8]
     heapify(n=5, i=0):
       2 vs 4,5 → troca com 5 → [5, 4, 2, 3, 1 | 7, 8]
       2 em [2]: filhos seriam [5] e [6], fora (n=5). Para.
     Heap: [5, 4, 2, 3, 1]

i=4: troca a[0]=5 com a[4]=1  →  [1, 4, 2, 3 | 5, 7, 8]
     heapify(n=4, i=0):
       1 vs 4,2 → troca com 4 → [4, 1, 2, 3 | 5, 7, 8]
       1 em [1] vs 3[3] (dir=4, fora) → troca → [4, 3, 2, 1 | 5, 7, 8]
       1 em [3]: sem filhos. Para.
     Heap: [4, 3, 2, 1]

i=3: troca a[0]=4 com a[3]=1  →  [1, 3, 2 | 4, 5, 7, 8]
     heapify(n=3, i=0):
       1 vs 3,2 → troca com 3 → [3, 1, 2 | 4, 5, 7, 8]
       1 em [1]: sem filhos (n=3). Para.
     Heap: [3, 1, 2]

i=2: troca a[0]=3 com a[2]=2  →  [2, 1 | 3, 4, 5, 7, 8]
     heapify(n=2, i=0):
       2 vs 1[1] → 2 > 1. Sem troca. Para.
     Heap: [2, 1]

i=1: troca a[0]=2 com a[1]=1  →  [1 | 2, 3, 4, 5, 7, 8]
     heapify(n=1, i=0): sem filhos. Para.

══════════ RESULTADO ══════════
[1, 2, 3, 4, 5, 7, 8]   ✓ ordenado em ordem crescente

Por que o max-heap ordena em ordem crescente?

A cada iteração, o maior elemento restante (raiz do heap) é colocado na posição final do bloco ativo. Após n−1 iterações, o vetor está com os valores em ordem crescente: os maiores foram acumulando no final.

10. Complexidade e comparação com outros algoritmos

Resumo

Exercícios

1. O vetor [50, 40, 30, 20, 35, 25, 10, 15, 5] representa um max-heap? Justifique verificando a propriedade para cada nó interno.
2. Trace a inserção do valor 45 no max-heap [50, 40, 30, 20, 35, 25, 10, 15, 5]. Mostre o vetor após cada troca.
3. Trace a remoção do máximo do heap [80, 60, 70, 50, 55, 65, 40, 30, 45]. Mostre o vetor após cada troca do heapify.
4. Execute o build-heap bottom-up no vetor [3, 7, 1, 9, 4, 6, 2]. Mostre o estado do vetor após cada heapify.
5. Trace as primeiras três extrações do Heap Sort no vetor [9, 6, 8, 5, 3, 7, 4] (assuma que já está em max-heap). Mostre o vetor e o heap ativo após cada extração.
6. O Heap Sort é estável? Explique com um contra-exemplo usando os valores [2a, 2b, 1], onde 2a e 2b são dois elementos iguais.
7. Quantas comparações são realizadas no heapify de um heap com n = 127 elementos (árvore perfeitamente balanceada de altura 6) no pior caso? Generalize para n = 2^k − 1.
8. Explique por que o build-heap bottom-up é O(n) e não O(n log n), mesmo que cada heapify individual seja O(log n).
9. Compare Heap Sort com Merge Sort: qual garante pior caso O(n log n)? Qual é estável? Qual é in-place? Em que situação você escolheria cada um?

Índices:  [0]=50, [1]=40, [2]=30, [3]=20, [4]=35, [5]=25, [6]=10, [7]=15, [8]=5

Nó 50[0]: filhos 40[1], 30[2].  50 ≥ 40 e 50 ≥ 30.  ✓
Nó 40[1]: filhos 20[3], 35[4].  40 ≥ 20 e 40 ≥ 35.  ✓
Nó 30[2]: filhos 25[5], 10[6].  30 ≥ 25 e 30 ≥ 10.  ✓
Nó 20[3]: filhos 15[7], 5[8].   20 ≥ 15 e 20 ≥ 5.   ✓

Sim, é um max-heap válido.

Inserir 45 em [9]. Vetor: [50, 40, 30, 20, 35, 25, 10, 15, 5, 45]

i=9. Pai=(9-1)/2=4 → 35. 45 > 35 → troca.
[50, 40, 30, 20, 45, 25, 10, 15, 5, 35]

i=4. Pai=(4-1)/2=1 → 40. 45 > 40 → troca.
[50, 45, 30, 20, 40, 25, 10, 15, 5, 35]

i=1. Pai=(1-1)/2=0 → 50. 45 < 50 → para.

Resultado: [50, 45, 30, 20, 40, 25, 10, 15, 5, 35]

Vetor: [3, 7, 1, 9, 4, 6, 2]   (n=7, último interno: i=2)

i=2: nó=1[2], filhos: 6[5] e 2[6]. Maior: 6. 1 < 6 → troca.
[3, 7, 6, 9, 4, 1, 2]  (1 desceu para [5], sem filhos)

i=1: nó=7[1], filhos: 9[3] e 4[4]. Maior: 9. 7 < 9 → troca.
[3, 9, 6, 7, 4, 1, 2]  (7 em [3], sem filhos)

i=0: nó=3[0], filhos: 9[1] e 6[2]. Maior: 9. 3 < 9 → troca.
[9, 3, 6, 7, 4, 1, 2]
  3 em [1], filhos: 7[3] e 4[4]. Maior: 7. 3 < 7 → troca.
  [9, 7, 6, 3, 4, 1, 2]
  3 em [3]: sem filhos. Para.

Resultado: [9, 7, 6, 3, 4, 1, 2]
Verificação: 9≥7,6 ✓; 7≥3,4 ✓; 6≥1,2 ✓

∑ (altura do nó i) para i de 0 a n/2-1
= 0·(n/2) + 1·(n/4) + 2·(n/8) + ... + log(n)·1
= n · ∑ k/2^k  =  n · 2  =  O(n)