Projeto de Algoritmos
Home      |      Prefácio      |      Livros      |      Sítios WWW      |      Índice

Heapsort

Esta página examina um algoritmo relativamente sofisticado que rearranja um vetor dado em ordem crescente. Para que a descrição do algoritmo fique mais simples, é importante que os índices do vetor sejam  1..n  e não 0..n-1, como é usual em C.  Resumindo, nosso algoritmo

rearranja os elementos de um vetor v[1..n] de tal modo que ele fique em ordem crescente,

ou seja, de tal modo que tenhamos v[1] ≤ v[2] ≤ . . . ≤ v[n].  O algoritmo, conhecido como Heapsort, foi inventado por J.W.J. Williams  ["Algorithms 232 (heapsort)", Communications of the ACM, 7, p.347-348, 1964].

Veja o verbete Heapsort na Wikipedia.

Heap (árvore binária quase-completa)

O segredo do funcionamento do algoritmo é uma estrutura de dados conhecida como heap (= monte). Um max-heap é um vetor v[1..m] tal que [estou escrevendo m e não n de propósito]:

v[f/2]  ≥  v[f]

para f = 2, . . . , m.  Aqui, como no resto desta página, vamos convencionar que as expressões que figuram como índices de um vetor são sempre inteiras. Uma expressão da forma "f/2" significa  piso(f/2), ou seja, a parte inteira do quociente de f por 2.

Assim, se v[1..17] é um max-heap então, em particular, v[5] ≥ v[10] e v[5] ≥ v[11]:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
999 999 999 999 999 999 999 999 999 999 999 999 999 999 999 999 999

Estranha essa definição de max-heap, não? Talvez a coisa fique mais clara se encararmos a seqüência de índices 1..m como um árvore binária:

A figura abaixo procura desenhar um vetor v[1..55] de modo que cada filho fique na "camada" imediatamente inferior à do pai. O vetor é definido por v[i]=i e portanto longe está de ser um max-heap. Observe que cada "camada", exceto a última, tem duas vezes mais elementos que a "camada" anterior. Com isso, o número de "camadas" de v[1..m] é exatamente   1 + lg(m),  sendo lg(m) o piso de log2m.
 1
2 3
4 5 6 7
8 9 10 11 12 13 14 15
16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55

Uma vez entendido o conceito de pai e filho, podemos dizer que um vetor é um max-heap se o valor de todo pai é maior ou igual que o valor de qualquer de seus dois filhos (onde o valor de um índice p é v[p]).

Exercícios

  1. Mostre que todo vetor decrescente indexado por 1,2, . . .  é um max-heap. Mostre que a recíproca não é verdadeira.
  2. O vetor abaixo é um max-heap?

    161 41 101 141 71 91 31 21 81 17 16

  3. Mostre que v[1..m] é um max-heap se e somente se para cada índice p tem-se
    1. se 2p ≤ m então v[p] ≥ v[2p];
    2. se 2p+1 ≤ m então v[p] ≥ v[2p+1].
  4. Suponha que v[1..m] é um max-heap com m = 2k-1. Mostre que mais da metade dos elementos do vetor está na última "camada" do max-heap, ou seja, em   v[2k-1.. 2k-1].

A função peneira

O coração de qualquer algoritmo que manipule um max-heap é uma função que recebe um vetor arbitrário v[1..m] e um índice p

e faz v[p] "descer" para sua posição "correta".

Como se faz isso? A idéia é óbvia. Se v[p] ≥ v[2p] e v[p] ≥ v[2p+1] então não é preciso fazer nada. Se v[p] < v[2p] ≥ v[2p+1] então basta trocar v[p] com v[2p] e depois fazer v[2p] "descer" para sua posição "correta". Não é difícil imaginar o que se deve fazer nos demais casos.

Eis um exemplo com p=1. Cada linha da tabela é uma "foto" do vetor no início de uma iteração.
85 99 98 97 96 95 94 93 92 91 90 89 87 86
 
99 85 98 97 96 95 94 93 92 91 90 89 87 86
 
99 97 98 85 96 95 94 93 92 91 90 89 87 86
 
99 97 98 93 96 95 94 85 92 91 90 89 87 86

Eis uma versão iterativa da função. A variável f é sempre um filho de p; no início de cada iteração, f é ajustado de modo a ser o filho de maior valor de p. 

// Recebe p em 1..m e rearranja o vetor v[1..m] de modo 
// que o "subvetor" cuja "raiz" é p seja um max-heap.
// Supõe que os "subvetores" cujas "raizes" são filhos
// de p já são max-heaps.

void peneira (int p, int m, int v[])
{
   while (2*p <= m) {
      int x, f = 2*p;
      if (f < m && v[f] < v[f+1])  ++f;
      // f é o filho "mais valioso" de p
      if (v[p] >= v[f]) break;
      x = v[p], v[p] = v[f], v[f] = x;
      p = f;
   }
}

A seguinte implementação é um pouco melhor, porque faz menos trocas: 

// Recebe p em 1..m e rearranja o vetor v[1..m] de modo
// que o "subvetor" cuja "raiz" é p seja um max-heap.
// Supõe que os filhos de p são "raízes" de heaps.

void peneira (int p, int m, int v[])
{ 
   int x = v[p];
   while (2*p <= m) {
      int f = 2*p;
      if (f < m && v[f] < v[f+1])  ++f;
      if (x >= v[f]) break;
      v[p] = v[f];
      p = f;
   }
   v[p] = x;
}

A função peneira: desempenho

A função peneira é muito rápida. O consumo de tempo é proporcional ao número de comparações entre elementos do vetor, não passa de

2 log2m ,

mesmo no pior caso. De fato, há duas comparações por iteração e o número e iterações não passa de log2m, pois o valor de p pelo menos dobra a cada iteração.

Exercícios

  1. A seguinte alternativa para a função peneira funciona corretamente? 
    void peneira (int p, int m, int v[]) { 
   int x, f;                        
   for (f = 2*p; f <= m; f = 2*f) {
      if (f < m && v[f] < v[f+1])  ++f;
      p = f/2;
      if (v[p] >= v[f]) break;
      x = v[p], v[p] = v[f], v[f] = x;
   }
}
  2. Escreva uma versão recursiva da função peneira.
  3. Por que a seguinte implementação de peneira não funciona? 
    void peneira (int p, int m, int v[]) {
    int x;
    int f = 2*p;
    while (f <= m) {
       if (v[p] < v[f]) {
          x = v[p], v[p] = v[f], v[f] = x;
          p = f;
          f = 2*p;
       }
       else if (f < m && v[p] < v[f+1]) {
               x = v[p], v[p] = v[f+1], v[f+1] = x;
               p = f+1;
               f = 2*p;
            }
            else break;
    }
}

Por que um heap é útil?

Por que um max-heap é uma estrutura de dados tão poderosa? Suponha que v[1..m] é um max-heap; então

  1. a pergunta "qual o maior elemento de vetor?" pode ser respondida instantaneamente: o maior elemento do vetor é v[1];
  2. se o valor de v[1] for alterado, o max-heap pode ser restabelecido muito rapidamente: a operação peneira (1,m,v) não demora mais que log(m) para fazer o serviço;
  3. um vetor v[1..m] arbitrário pode ser transformado em um max-heap muito rapidamente: o comando 
       for (p = m/2; p >= 1; --p)  peneira (p, m, v);

    faz o serviço em tempo proporcional a  m.  (É fácil ver que o consumo de tempo é limitado por (m log(m))/2, pois o tempo gasto em cada uma das m/2 iterações é limitado por log(m).  É um pouco mais difícil verificar que o tempo é, na verdade, limitado por m apenas.)

Exercícios

  1. Mostre que o fragmento de programa abaixo faz no máximo m comparações entre elementos do vetor. 
       for (p = m/2; p >= 1; --p)  peneira (p, m, v);
  2. O fragmento de programa abaixo transforma um vetor arbitrário v[1..m] em max-heap? 
       for (p = 1; p <= m/2; ++p)  peneira (p, m, v);
  3. Critique a seguinte idéia: para transformar um vetor arbitrário em max-heap, basta colocá-lo em ordem decrescente.
  4. Escreva uma função ff que receba um vetor v e um índice k tais que  v[1..k-1]  é um max-heap e transforme  v[1..k]  em max-heap. Sua função deve fazer no máximo 2 log(k) comparações entre elementos do vetor.   Agora use a função ff para construir uma função que transforme qualquer vetor v[1..m] em max-heap. Sua função deve fazer no máximo  2 m log(m)  comparações entre elementos do vetor.

O algoritmo heapsort

Não é difícil juntar tudo que dissemos acima para obter um algoritmo que coloque v[1..n] em ordem crescente. 

// Rearranja os elementos do vetor v[1..n] 
// de modo que fiquem em ordem crescente

void heapsort (int n, int v[])
{
   int p, m, x;
   for (p = n/2; p >= 1; --p)
      peneira (p, n, v);
   for (m = n; m >= 2; --m) {
      x = v[1], v[1] = v[m], v[m] = x;
      peneira (1, m-1, v);
   }
}

O comando for transforma o vetor em um max-heap recorrendo cerca de n/2 vezes à função peneira. Feito isso, temos um processo iterativo controlado pelo segundo for. No início de cada iteração valem as seguinte invariantes:

É claro que v[1..n] estará em ordem crescente quando m for igual a 1.
1 m n
888 777 666 555 444 333 222 111 000 999 999 999 999 999
max-heap, elementos pequenos crescente, elementos grandes

Heapsort: desempenho

Quanto tempo o heapsort leva para fazer o serviço? O tempo é proporcional ao número de comparações entre elementos do vetor, e esse número não passa de

3 n log2n ,

mesmo no pior caso. De fato, o primeiro for constrói o max-heap inicial e faz no máximo  n log(n)  comparações entre elementos do vetor.  (Uma análise mais cuidadosa revela que o número de comparações não passa de n).  O segundo for executa cerca de n chamadas de peneira e cada uma dessas chamadas faz no máximo  2 log(n)  comparações entre elementos do vetor.

Heapsort: animações

Veja applets de animação do algoritmo:

Exercícios

  1. Use o heapsort para ordenar o vetor  16 15 14 13 12 11 10 9 8 7 6 5 4.
  2. Suponha que o vetor v[1..n] é um max-heap. O seguinte fragmento de código rearranja o vetor em ordem crescente? 
       for (m = n; m >= 2; --m) {
      int x = v[1];
      for (j = 1; j < m; ++j) v[j] = v[j+1];
      v[m] = x;
   }
  3. Implemente um max-heap com ponteiros. Cada célula terá um valor e três ponteiros: um aponta o pai da célula, outro aponta o filho direito e outro aponta o filho esquerdo. Escreva uma versão da função peneira para um max-heap implementado com ponteiros.
  4. Suponha que v[1..m] é um max-heap. Suponha que i < j e v[i] < v[j]. Se os valores de v[i] e v[j] forem trocados, v[1..m] continuará sendo um max-heap?  Repita o exercício sob a hipótese v[i] > v[j].
  5. Escreva uma função HS que receba um max-heap v[1..n] e rearranje o vetor de modo que ele fique em ordem crescente. Tire proveito de que o vetor dado não é arbitrário.  Sugestão: Digamos que um vetor v[1..m] é um quase-max-heap se

    v[f/2] ≥ v[f]   para f = 4, . . . , m.

    Escreva uma função H que receba um quase-max-heap v[1..m] e transforme-o em um max-heap. (Basta fazer uma versão ligeiramente especializada de peneira.) Use H para escrever HS.

  6. Escreva uma função rearranje um vetor v[1..n] dado de modo que ele fique em ordem decrescente.  Sugestão: Adapte a definição de max-heap para o problema em questão. Reescreva a função peneira.

 

The Sorting Algorithm Demo:  animação de algoritmos de ordenação. Página de Istvan Simon na Universidade da California em Hayward. (Istvan foi professor aqui do IME-USP).
URL of this site: www.ime.usp.br/~pf/algoritmos/
1998 | Last modified: Tue Nov 28 11:52:32 BRST 2006
Paulo Feofiloff
IME-USP

Valid HTML 4.0!     Valid CSS!