A estrutura heap

Esta página estuda as propriedades da estrutura de dados binary heap inventada por J.W.J. Williams. A estrutura é muito útil na a construção de filas-com-prioridades e está no coração do algoritmo Heapsort.

Árvore binária armazenada em um vetor

Suponha dado um vetor A[1 .. n]. Por enquanto, os valores armazenados no vetor não nos interessam; só interessam certas relações entre índices. Para todo índice i, diremos que

É claro que isso deve ser entendido com cautela:  o índice 1 não tem pai;  um índice i só tem filho esquerdo se 2i ≤ n;  e i só tem filho direito se 2i+1 ≤ n.

i
┌──┴──┐
2i ──┴─ 2i+1

Com essa ideia de pais e filhos, o vetor adquire uma estrutura de árvore binária quase completa e os elementos do vetor, identificados pelos índices 1 a n, passam a ser chamados nós.

A figura abaixo sugere uma maneira de encarar o vetor. Cada caixa é um nó da árvore binária quase completa A[1 .. 55]. (O número dentro de cada caixa é i e não A[i].)

1 0
2 3 1
4 5 6 7 2
8 9 10 11 12 13 14 15 3
16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 4
32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 5

Os números na coluna à direita indicam os níveis da árvore. Cada nível p, exceto talvez o último, tem exatamente 2p nós e esses nós são  2p, 2p+1, 2p+2, … , 2p+1−1. (O último nível pode ter menos nós.)  O nó i pertence ao nível

  lg i⌋ .  (*)

Portanto, o número total de níveis é 1 + ⌊lg n. Uma propriedade simples mas importante:  o número de nós em qualquer nível p (exceto talvez o último) é  1+S, onde S é a soma do número de nós nos níveis 0, … , p−1.

O nó 1 é a raiz da árvore. Qualquer nó i é raiz da subárvore formada por i, seus filhos, seus netos, etc. Ou seja, a subárvore com raiz i é o vetor

A [i, 2i, 2i+1, 4i, 4i+1, 4i+2, 4i+3, 8i, … , 8i+7, … ].

Exemplo: a figura abaixo destaca a subárvore cuja raiz é 13.

1 0
2 3 1
4 5 6 7 2
8 9 10 11 12 13 14 15 3
16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 4
32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 5

Exercícios 1

  1. O modo de definir pais e filhos que usamos acima pode ser aplicada a um vetor cujo primeiro índice é 0?
  2. Suponha dada uma árvore binária quase completa com n nós. Digamos que a subárvore esquerda de nossa árvore tem e nós e a subárvore direita tem d nós. Mostre que  de ≤ ⌊2n/3⌋.

Altura de um nó

O conceito de altura é complementar ao conceito de nível. A altura (= heigth) de um nó i em A[1 .. n] é o número

  ⌊lg (n/i)⌋ .  (**)

Assim, a altura de um nó i não é maior que a diferença entre os níveis de ni, mas pode ser menor que essa diferença.

A altura de um nó i é o comprimento do mais longo caminho da forma  filho(i), filho(filho(i)), …   Os nós que têm altura 0 são chamados folhas. O nó n, por exemplo, é uma folha.

Não é difícil verificar, a partir de nossa definição de altura, que há no máximo  n/2h+1  nós de altura h.

Max-heap

Em termos um tanto vagos, um max-heap (ou árvore hierárquica) é uma árvore binária quase completa em que cada pai é maior ou igual que qualquer de seus filhos. (Se trocássemos maior ou igual por menor ou igual teríamos um min-heap.)  Eis uma definição mais precisa:  Um vetor A[1 .. n] é um max-heap se

A[⌊i/2⌋] ≥ A[i]

para i = 2, … , n. Em outras palavras, A[1 .. n] é um max-heap se  A[ j] ≥ A[2j]  e  A[ j] ≥ A[2j+1]  sempre que os índices não ultrapassam n.

Às vezes convém aplicar a palavra heap apenas a uma parte do vetor: dado um índice i, diremos que a subárvore com raiz i é um max-heap se

A[i] ≥ A[2i], A[i] ≥ A[2i+1], A[2i] ≥ A[4i], A[2i] ≥ A[4i+1], etc.

Por que um heap é uma estrutura de dados tão útil? Eis algumas razões:

Exercícios 2

  1. Suponha que A[1 .. n] é um max-heap. Mostre A[1] é um elemento máximo do vetor.
  2. Se A[1 .. n] é um max-heap, onde pode estar o segundo maior elemento do vetor?

O algoritmo Corrige-Descendo

A principal ferramenta de manipulação de um heap é o algoritmo que discutiremos a seguir.  O algoritmo resolve o seguinte pequeno problema:

Problema:  Dado um vetor A[1 .. n] e um índice i tal que a subárvore com raiz  2i  é um max-heap e a subárvore com raiz  2i+1  é um max-heap, rearranjar o vetor de modo que a subárvore com raiz  i  seja um max-heap.

A ideia do algoritmo é simples: se A[i] é maior ou igual que seus filhos então não é preciso fazer nada; senão, troque A[i] com o maior dos filhos e repita o processo para o filho envolvido na troca.

Em inglês, o algoritmo é conhecido como Heapify, ou Sieve, ou Fix-Down, ou Shake-Down. Em português, poderíamos usar o nome Peneira, mas vou preferir Corrige-Descendo, porque é mais descritivo.

Corrige-Descendo (A, n, i)
1 . j := i
2 . enquanto 2 jn
3 .ooo f := 2 j
4 .ooo se f < n e A[f] < A[f + 1]
5 .oooooo f := f + 1
6 .ooo se A[ j] ≥ A[f]
7 .oooooo j := n
8 .ooo senão troque A[ j] :=: A[f]
9 .ooo senão j := f

[Tiago Togores apontou um lamentável erro na versão anterior do código.]  Para provar que o algoritmo está correto basta observar o seguinte invariante, válido no início de cada iteração, imediatamente antes da comparação de 2j com n:

a subárvore com raiz i é um max-heap exceto talvez por uma falha no nó j, onde as desigualdades A[j] ≥ A[2j] e A[j] ≥ A[2j+1] podem não estar satisfeitas.

O consumo de tempo do algoritmo é proporcional ao número de repetições do bloco de linhas 3 a 9. Para calcular esse número, examine a sequência de valores da variável j. No pior caso, j assume os valores i, 2i, 4i, … , 2ki, …   continuando enquanto tivermos 2ki ≤ n. O maior valor de k nessa sequência será  ⌊lg (n/i)⌋. Portanto, o número de iterações será ⌊lg (n/i)⌋ no pior caso e o consumo total de tempo será

  Ο(lg (n/i)) . (***)

Portanto, o consumo de tempo no pior caso é proporcional à altura do nó i na árvore.

Se i = 1, por exemplo, o consumo de tempo é Ο(lg n). Se i = 2, o consumo também é Ο(lg n). Se i é maior que n/2, o consumo também é constante (ou seja, não depende de n nem de i).

Exercícios 3

  1. Prove que o invariante do algoritmo Corrige-Descendo está correto.
  2. A doutrina da análise de algoritmos diz que o consumo de tempo de um algoritmo deve ser expresso em função do tamanho das instâncias. Aplique essa doutrina ao consumo de tempo de Corrige-Descendo.
  3. Escreva uma versão recursiva do algoritmo Corrige-Descendo. Faça uma análise do consumo de tempo de seu algoritmo.

Construção de um max-heap

O algoritmo abaixo recebe um vetor A[1 .. n] e rearranja seus elementos de modo a transformar o vetor em um max-heap.

Constrói-Max-Heap (A, n)
1 . para i := ⌊n/2⌋ decrescendo até 1
2 .ooo Corrige-Descendo (A, n, i)

O algoritmo Corrige-Descendo é invocado n/2⌋ vezes. Cada invocação consome Ο(lg n) unidades de tempo. Portanto, o consumo de tempo total no pior caso é  Ο(n lg n). Mas esta estimativa é excessivamente folgada. Mostraremos a seguir que o consumo é de apenas

Ο(n)

unidades de tempo, mesmo no pior caso.

Adote a abreviatura p = ⌊lg n. Então a árvore A[1 .. n] tem p+1 níveis, numerados de 0 a p. O algoritmo começa a trabalhar no nível p−1. Neste nível, podemos dizer que cada invocação de Corrige-Descendo na linha 2 consome 1 unidade de tempo, pois cada nó tem altura 1. Como há no máximo 2p−1 nós neste nível, o consumo para o nível não passa de

1·2p−1.

Se repetirmos esse raciocínio para os níveis  p−2, p−3, etc., veremos que o consumo de tempo total de Constrói-Max-Heap não passa de

1·2p−1 + 2·2p−2 + 3·2p−3 + … ,

ou seja, 2p · (1·2−1 + 2·2−2 + 3·2−3 + … ). Como a soma entre parênteses é menor que 2 (veja exercício abaixo), o algoritmo consome no máximo  2·2p  unidades de tempo. Como p ≤ lg n, o tempo gasto por Constrói-Max-Heap não passa de

2n.

(É interessante refazer essa prova em linguagem contábil, conforme exercício abaixo.)

Resumindo:  Constrói-Max-Heap consome  Ο(n)  unidades de tempo quando aplicado a um vetor com n elementos. O algoritmo é, portanto, linear. Tudo se passa como se cada uma das n/2 execuções de Corrige-Descendo consumisse apenas Ο(1) unidades de tempo. Em linguagem mais técnica, dizemos que o consumo amortizado de cada execução de Corrige-Descendo é Ο(1).

Exercícios 4

  1. Mostre que para qualquer número x tal que 0 < x < 1 tem-se  x + 2x2 + 3x3 + 4x4 + …  <  x/(1−x)2.
  2. Mostre que o seguinte fragmento de código não transforma A[1 .. n] em max-heap:
    . para i := 1 até n
    .ooo Corrige-Descendo (A, n, i)
  3. O seguinte algoritmo transforma A[1 .. n] em max-heap?
    . para k := n decrescendo até 2
    .ooo se A[⌊k/2⌋] < A[k]
    .oooooo troque A[⌊k/2⌋] :=: A[k]
  4. ★ Mostramos acima que Constrói-Max-Heap consome apenas Ο(n) unidades de tempo. Refaça a prova em linguagem contábil.

O algoritmo Corrige-Subindo

O seguinte algoritmo supõe que A[1 .. m−1] é um max-heap e rearranja A[1 .. m] de modo a transformar o vetor em um max-heap.

Corrige-Subindo (A, m)
1 . i := m
2 . enquanto i ≥ 2 e A[⌊i/2⌋] < A[i]
3 .ooo troque A[⌊i/2⌋] :=: A[i]
4 .ooo i := ⌊i/2⌋

Invariante: No começo de cada iteração, imediatamente antes da comparação de i com 2, temos A[ancestral(j)] ≥ A[j] para todo j diferente de i, sendo ancestral(j) qualquer índice do conjunto { pai(j), pai(pai(j)), pai(pai(pai(j))), … }.

Exercícios 5

  1. Prove que o invariante do algoritmo Corrige-Subindo está correto.
  2. Escreva a função Corrige-Subindo em estilo recursivo. Faça uma análise do consumo de tempo do seu algoritmo.
  3. Prove que o fragmento de código transforma o vetor A[1 .. n] em max-heap. Quanto tempo o algoritmo consome no pior caso?
    . para m := 2 até n
    .ooo Corrige-Subindo (A, m)
  4. O seguinte fragmento de código transforma o vetor A[1 .. n] em max-heap?
    . para m := n decrescendo até 2
    .ooo Corrige-Subindo (A, m)

Min-heap

Um min-heap é o objeto complementar ao max--heap:  cada pai é menor ou igual que qualquer de seus filhos. Mais precisamente, um vetor A[1 .. n] é um min-heap se A[⌊i/2⌋] ≤ A[i] para i = 2, … , n. É fácil adaptar os algoritmos acima para tratar de min-heaps.