MAC0338   Análise de Algoritmos

 

Análise do algoritmo Heapsort

Esta página é um resumo do capítulo 7 de CLR. O capítulo discute o algoritmo HEAPSORT, inventado por J.W.J. Williams1.

 

Á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. Diremos que

É claro que isso deve ser entendido com cautela: o índice 0 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 de nós. A figura abaixo sugere uma maneira de encarar o vetor; nesta figura, os números representam índices e não valores dos elementos do vetor.

 
  01 0
02 03 1
04 05 06 07 2
08 09 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 5

 

Os números do lado direito indicam os níveis da árvore. Cada nível p exceto o último tem exatamente 2p elementos e esses elementos são

2p,   2p+1,   2p+2, . . . ,   2p+1-1.

(O último nível pode ter menos elementos.) Todo nó i pertence ao nível

chão(lg(i)).

Portanto, o número total de níveis é 1 + chão(lg(n)).

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 destaca a subárvore com raiz 13.

 
  01 0
02 03 1
04 05 06 07 2
08 09 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 5

 

 

Exercícios

  1. O algoritmo abaixo trabalha sobre um vetor A[1..m]. Que efeito o algoritmo tem sobre o vetor? Justifique de maneira precisa. (Uma boa maneira de fazer isso é dizer que "cara" tem o vetor no início de cada iteração "para" e no início de cada iteração "enquanto".) 
        para j := 2 até m faca
      i := j
      enquanto i >= 2 e A[i/2] < A[i] faca
         troque A[i/2] :=: A[i]
         i := i/2

    Delimite (usando notação Theta) o tempo total que o algoritmo consome no pior caso. Justifique.

 

Heap

Definição um tanto vaga: um heap é uma árvore binária quase completa em que cada pai é maior ou igual que qualquer de seus filhos. Definição mais precisa: Um vetor A[1..n] é um heap (= monte) se

A[chão(i/2)]   >=   A[i]

para i = 2, . . . , n. Em outras palavras, A[1..n] é um heap se A[j] >= A[2j] e A[j] >= A[2j+1] sempre que os índices não ultrapassarem 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 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:

 

O algoritmo auxiliar PENEIRA

Suponha dado um vetor A[1..n] e um índice i tal que a subárvore com raiz 2i é um heap e a subárvore com raiz 2i+1 é um heap.  PROBLEMA BÁSICO: Rearranjar o vetor de modo que a subárvore com raiz i seja um heap.

Como resolver o problema? A idéia 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.

PENEIRA (A, n, i)
  e := 2i
  d := 2i+1
  se e <= n   e   A[e] > A[i]
      então f := e senão f := i
  se d <= n   e   A[d] > A[f]
      então f := d
  se f > i então
      troque A[f] :=: A[i]
      PENEIRA (A, n, f)

Quanto tempo o algoritmo consome no pior caso? A primeira coisa a fazer é escolher uma boa medida do "tamanho" do problema. O valor de n não é uma boa medida (por que?). Uma medida melhor é a diferença de nível entre o nó i e o nó n, ou seja,

chão(lg(n)) - chão(lg(i)).

Esse número é conhecido como altura do nó i. (Cuidado: esta definição de altura é ligeiramente diferente, e mais simples, que a do CLR.)

Digamos, então, que o tempo de pior caso do algoritmo é T(h), onde h é a altura do nó i. A figura abaixo mostra o consumo de tempo de cada linha do algoritmo:

PENEIRA (A, n, i)
  e := 2i
  d := 2i+1
  se e <= n   e   A[e] > A[i]
      então f := e senão f := i
  se d <= n   e   A[d] > A[f]
      então f := d
  se f <> i então
      troque A[f] :=: A[i]
      PENEIRA (A, n, f) 		 
1 
1 
1 
1 
1 
1 
1 
1 
T(h-1) 

A justificativa do "T(h-1)" é fácil: se f é diferente de i então o nível de f é exatamente uma unidade maior que o nível de i.

Portanto, T(h) é dado pela seguinte recorrência:   T(0) <= 7   e   T(h) <= T(h-1) + 8  para h = 1, 2, 3, etc.  Logo, T(h) <= 7 + 8h.   Se preferir uma expressão mais simples, você pode dizer que

T(h)   <=   15 h

para h = 1, 2, 3, etc.  Em termos dos parâmetros n e i do algoritmo, podemos dizer que o consumo de tempo no pior caso é

O(chão(lg(n)) - chão(lg(i))).

Em particular, é verdade que o consumo de tempo é O(chão(lg(n))), mas esta delimitação é grosseira demais para o cálculo que faremos na próxima seção.

 

Exercícios

  1. Encontre uma fórmula fechada para a função f definida pela seguinte recorrência: f(1) = 7 e

    f(k)   =   f(2k/3) + 8

    quando k é uma potência de 3/2.  SOLUÇÃO: Supondo k = (3/2)j, temos  f((3/2)j) = 

                       =  f((3/2)j-1) + 8
                   =  f((3/2)j-2) + 8 + 8
                   =  f((3/2)j-3) + 8×3
                   =  f((3/2)j-j) + 8×j
                   =  7 + 8×j .

    Logo, f(k) = 8 log3/2(k) + 7.

     

  2. Digamos que um algoritmo X age sobre uma árvore binária quase completa com k nós. O algoritmo é recursivo e a recursão reduz o problema à subárvore esquerda ou à subárvore direita da árvore dada. Digamos que o tempo de pior caso do algoritmo, T(k), satisfaz a seguinte recorrência: T(1) <= 7 e

    T(k) <= T(chão(2k/3)) + 8

    para k maior que 1. (Veja exercício.) Mostre que T(k) <= 16 lg(k) para k = 2, 3, 4, . . .

    SOLUÇÃO: A desigualdade vale com k = 2 pois  T(2) = 15  e  16 lg(2) = 16. Agora suponha que k > 2. Como lg(chão(2k/3)) <= lg(2k/3), teremos 

              T(k)  <=  16lg(2k/3) + 8
   
                 =  16(1 + lg(k) - lg(3)) + 8
 
                 =  16lg(k) + 24 - 16lg(3)
   
                <=  16lg(k) ,

    uma vez que 16lg(3) > 24.

 

Construção de um heap

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

CONSTRÓI-HEAP (A, n)
  para i := chão(n/2) decrescendo até 1 faça
      PENEIRA (A, n, i)

O algoritmo PENEIRA é chamado chão(n/2) vezes. Cada chamada não consome mais que 15 h unidades de tempo, onde h é a altura de i. Como h <= lg(n), podemos dizer que o consumo de tempo do algoritmo no pior caso é

O(n lg(n)).

Mas esta estimativa é muito folgada: na verdade, o consumo é O(n), mesmo no pior caso. É o que veremos a seguir. Adote a abreviatura p = chão(lg(n)). Então a árvore tem p+1 níveis, numerados de 0 a p. O algoritmo começa a trabalhar no nível p-1. Neste nível, cada chamada do PENEIRA consome não mais que 15 unidades de tempo, pois cada nó tem altura 1. Como há 2p-1 nós neste nível, o consumo total é

<=   15×2p-1.

Se continuarmos esse raciocínio com os níveis p-2, . . . , 0 chegaremos à conclusão de que o tempo gasto não passa de

15 ×(1×2p-1 + 2×2p-2 + 3×2p-3 + . . . ).

A figura resume o raciocínio. A coluna direita dá o custo das execuções de PENEIRA. Para simplificar, foram omitidos os custos das linhas "para ...".

CONSTRÓI-HEAP (A, n)
  p := chão(lg(n))
  para i := chão(n/2) decrescendo até 2p-1 faça
      PENEIRA (A, n, i)
  para i := 2p-1-1 decrescendo até 2p-2 faça
      PENEIRA (A, n, i)
  para i := 2p-2-1 decrescendo até 2p-3 faça
      PENEIRA (A, n, i)
  . . .
  para i := 21-1 decrescendo até 20 faça
      PENEIRA (A, n, i)
  
 
 
15 × 1 × 2p-1 
 
15 × 2 × 2p-2 
 
15 × 3 × 2p-3 
 
 
15 × p × 20 

Mas a soma 1×2-1 + 2×2-2 + 3×2-3 + . . .    é menor que 2 (veja lista de exercícios). Logo, o tempo gasto pelo algoritmo não passa de

15×2p.

Como p <= lg(n), o tempo gasto não passa de  15 n .  Concluímos assim a verificação de que o consumo de tempo de CONSTRÓI-HEAP(A, n)  é  O(n).

 

Heapsort

Finalmente, vamos juntar todas as peças do quebra cabeças. O algoritmo abaixo recebe rearranja um vetor A[1..N] (não confunda N com n) de modo que ele fique em ordem crescente.

HEAPSORT (A, N)
  CONSTRÓI-HEAP (A, N)
  para n := N, N-1, . . . , 2  faça
      A[1] :=: A[n]
      PENEIRA (A, n-1, 1)

Para entender como a coisa funciona, observe que no início de cada iteração do "para"

o vetor A[1..n] é um heap,
A[1..n]   <=   A[n+1..N] e
o vetor A[n+1..N] está em ordem crescente.

(Note como o algoritmo consegue fazer o serviço seu usar vertor auxiliar!) É claro que A[1..N] estará em ordem crescente quando n for igual a 1.
1 n N
888 777 666 555 444 333 222 111 000 999 999 999 999 999
heap, elementos pequenos crescente, elementos grandes

É fácil verificar que o consumo de tempo do algoritmo é O(N lg(N)) no pior caso.

 

Exercícios

  1. Escreva um algoritmo iterativo que faça o seguinte: recebe um vetor A[1..N] que é um heap e rearranja o vetor de modo que ele fique crescente. Faça uma análise do consumo de tempo do seu algoritmo no pior caso.

    [Solução]

 

 

Notas

1   J.W.J. Williams, "Algorithms 232 (heapsort)", Communications of the ACM, 7, p.347-348, 1964.

 

 

  [<<MAC0338]  

Atualizado em 6-ABR-1999
Paulo Feofiloff
IME-USP