Análise de Algoritmos | Aulas | Bibliografia | WWW | 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 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 que temos 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  (veja definição de piso),
• 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 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].)

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

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

Exercícios

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

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  (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  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 "consertado" muito rapidamente.
• Um vetor A[1..n] arbitrário pode ser transformado em um max-heap muito rapidamente.

Exercícios

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

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

Exercícios

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

Exercícios

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

Exercícios

URL of this site: http://www.ime.usp.br/~pf/analise_de_algoritmos/
Last modified: Fri Jul 1 10:14:34 BRT 2011
Paulo Feofiloff
Departamento de Ciência da Computação
Instituto de Matemática e Estatística da USP