A estrutura heap

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

Esta página é inspirada no capítulo 6 de CLRS.  Veja também o verbete Heapsort na Wikipedia.

Á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 história 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⌋  (*)

(veja definição de lg).  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. 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   d ≤ e ≤ ⌊2n/3⌋.

Altura de um nó

O conceito de altura é complementar ao conceito de nível. A altura 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  (veja a definição de teto).

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  Aj] ≥ A[2j]  e  Aj] ≥ 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

  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)
_ ji
_ enquanto  2 jn  faça
____ f ← 2 j
____ se  f < n  e  A[f] < A[f + 1]
_______ então  ff + 1
____ se  Aj] ≥ A[f ]
_______ então  jn
_______ senão  troque  Aj] ↔ A[f ]
_______ senão  jf

[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 iteraçõ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

  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)
_ para  i ← ⌊n/2⌋  decrescendo até  1  faça
____ 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

  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  faça
    ____ Corrige-Descendo (A, n, i)
  3. O seguinte algoritmo transforma A[1..n] em max-heap?
    _ para kn decrescendo até 2 faça
    ____ se A[⌊k/2⌋] < A[k]
    _______ então troque A[⌊k/2⌋] ↔ A[k]
  4. [Interessante]  Mostramos acima que Constrói-Max-Heap consome apenas Ο(n) unidades de tempo.  Refaça a prova em linguagem contábil.  [Solução]

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 _ im
2 _ enquanto i ≥ 2 e A[⌊i/2⌋] < A[i] faça
3 ____ troque A[⌊i/2⌋] ↔ A[i]
4 ____ 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

  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 faça
    ____ Corrige-Subindo (A, m)
  4. O seguinte fragmento de código transforma o vetor A[1..n] em max-heap?
    _ para  mn decrescendo até 2 faça
    ____ 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.

Valid HTML 4.01 Strict Valid CSS!