Análise de Algoritmos | Aulas | Dicionário | Índice

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

• ⌊i/2⌋  é o pai do índice i,
• 2i  é o filho esquerdo de i,
• 2i+1  é o filho direito de i

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

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].)

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

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.

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

Assim, a altura de um nó i não é maior que a diferença entre os níveis de n e i, 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/2^h+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:

• Se A[1 .. n] é um max-heap, é muito fácil encontrar um elemento máximo do vetor: A[1] é máximo.
• Se A[1 .. n] é um max-heap e se o valor de A[1] for alterado, o max-heap pode ser corrigido muito rapidamente.
• Um vetor A[1 .. n] arbitrário pode ser transformado em um max-heap muito rapidamente.

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.

[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, … , 2^ki, …   continuando enquanto tivermos 2^ki ≤ 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á

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

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.

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 2^p−1 nós neste nível, o consumo para o nível não passa de

1·2^p−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·2^p−1 + 2·2^p−2 + 3·2^p−3 + … ,

ou seja, 2^p · (1·2⁻¹ + 2·2⁻² + 3·2⁻³ + … ). Como a soma entre parênteses é menor que 2 (veja exercício abaixo), o algoritmo consome no máximo  2·2^p  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).

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.

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))), … }.

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.