[Curso de AeED - Aula 06] [Algoritmo] Ordenação - Heapsort

[pile-of-sand-7283847_orig.png]
Este capítulo examina um importante e sofisticado algoritmo de ordenação de vetores.  O algoritmo que discutiremos rearranja os elementos de um vetor v[1..n] de modo que eles fiquem em ordem crescente, ou seja, de modo que tenhamos v[1] ≤ v[2] ≤  . . .  ≤ v[n].  O algoritmo, conhecido como Heapsort, foi inventado por J.W.J. Williams em 1964.
Estamos supondo que os índices do vetor são  1..n  e não 0..n-1 como é usual em C.  Essa convenção torna o código um pouco mais simples. O Heapsort é muito eficiente: consome tempo proporcional a  n log n  mesmo no pior caso.  A base do algoritmo é uma fila de prioridades muito eficiente.

Vetores e árvores binárias

Antes de começar a discutir o Heapsort, precisamos aprender a enxergar a árvore binária que está escondida em qualquer vetor.  Todo vetor  v[1..m]  pode ser encarado como uma árvore binária da seguinte maneira:
  • o índice 1 é a raiz da árvore;
  • pai de qualquer índice  f  é  f/2  (é claro que 1 não tem pai);
  • filho esquerdo de um índice  p  é  2p  (esse filho só existe se 2p ≤ m );
  • filho direito de  p  é  2p+1  (esse filho só existe se 2p+1 ≤ m).
Aqui, como no resto deste capítulo, vamos convencionar que as expressões que figuram como índices de um vetor são sempre inteiras. Assim, uma expressão da forma f/2 significa  ⌊f/2⌋ , ou seja, o piso de f/2.
1234567891011121314
999999999999999999999999999999999999999999
Para tornar a árvore binária mais evidente, podemos desenhar o vetor em camadas de tal modo que cada filho fique na camada seguinte à do pai.  A figura abaixo é um tal desenho do vetor v[1..56].  (Os números nas caixas são os índices i e não os valores v[i].)  Observe que cada camada, exceto talvez a última, tem duas vezes mais elementos que a camada anterior. Com isso, o número de camadas de um vetor v[1..m] é exatamente   1 + lg(m),  sendo lg(m) o piso de log m.
1
23
4567
89101112131415
16171819202122232425262728293031
32333435363738394041424344454647484950515253545556

Exercícios 1

  1. Seja m um número da forma 2k-1. Mostre que mais da metade dos elementos de qualquer vetor v[1..m] está na última camada.

Heap

O segredo do algoritmo Heapsort é uma estrutura de dados, conhecida como heap, que enxerga o vetor como uma árvores binária.  (Há dois sabores da estrutura: max-heap e min-heap, mas trataremos aqui apenas do primeiro, omitindo o prefixo max.)  Um heap (= monte) é um vetor v[1..m] tal que
v[f/2] ≥ v[f]
para f = 2, . . . , m .  (Como já dissemos acima, a expressão f/2 deve ser entendida como  ⌊f/2⌋.)   De maneira mais informal, podemos dizer que um vetor v[1..m]é um heap se o valor de todo pai é maior ou igual ao valor de qualquer de seus dois filhos, sendo v[i] o valor de i.
1234567891011121314
999888777555666777555222333444111333666333
Para entender o Heapsort, será preciso tratar, às vezes, de heaps com defeitos:  diremos que um vetor v[1..m] é um heap exceto talvez pelo índice k se a desigualdade v[f/2] ≥ v[f] vale para todo f diferente de k.

Exercícios 2

  1. O vetor  161 41 101 141 71 91 31 21 81 17 16  é um heap?
  2. Mostre que todo vetor decrescente é um heap. Mostre que a recíproca não é verdadeira.
  3. Escreva uma função que decida se um vetor v[1..m] é ou não um heap.
  4. Mostre que v[1..m] é um heap se e somente se cada índice p tem as seguintes propriedades:  (a) v[p] ≥ v[2p] se 2p ≤ m  e  (b) v[p] ≥ v[2p+1] se 2p+1 ≤ m.
  5. Suponha que v[1..m] é um heap e p é um índice menor que m/2.  É verdade que v[2p] ≥ v[2p+1]?  É verdade que v[2p] ≤ v[2p+1]
  6. Suponha que v[1..m] é um heap e sejam i < j dois índices tais que v[i] < v[j]. Se v[i] e v[j] forem intercambiados, v[1..m] continuará sendo um heap?  Repita o exercício sob a hipótese v[i] > v[j].
  7. Suponha que v[1..m] é um heap e que os elementos do vetor são diferentes entre si.  É claro que o maior elemento do vetor está no índice 1.  Onde pode estar o segundo maior elemento?  Onde pode estar o terceiro maior elemento?  É verdade que o terceiro maior elemento é filho do segundo maior elemento?

Construção de um heap

É fácil rearranjar um vetor v[1..m] para que ele se torne um heap.  A idea é repetir o seguinte processo enquanto o valor de um filho for maior que o de seu pai: troque os valores de pai e filho e suba um passo em direção à raiz.  Mais precisamente, se v[f/2] < v[f], faça troca (v[f/2], v[f]) e em seguida f = f/2.  A operação de troca é definida assim:
#define troca (A, B) { int t = A; A = B; B = t; }
Eis o código completo:
// Rearranja um vetor v[1..m] de modo a
// transformá-lo em heap.

static void 
constroiHeap (int m, int v[])
{
   int k; 
   for (k = 1; k < m; ++k) {                   
      // v[1..k] é um heap
      int f = k+1;
      while (f > 1 && v[f/2] < v[f]) {  // 5
         troca (v[f/2], v[f]);          // 6
         f /= 2;                        // 7
      }
   }
}
(A palavra-chave static está aí apenas para indicar que constroiHeap é uma função auxiliar e não pode ser invocada diretamente pelo usuário final do Heapsort.)  
No início de cada iteração controlada pelo for, o vetor v[1..k] é um heap.  No curso da iteração, v[k+1] é incorporado ao heap.  Para isso, v[k+1] sobe em direção à raiz até encontrar sua posição correta no heap.
Em cada iteração do bloco de linhas 6-7, o índice f pula de uma camada do vetor para a anterior. Portanto, esse bloco de linhas é repetido no máximo lg(k) vezes para cada k fixo. Segue daí que o número total de comparações entre elementos do vetor (todas acontecem na linha 5 do código) não passa de
m lg(m) .
(Como veremos adiante, é possível transformar v[1..m] em heap com m comparações apenas.)

Exercícios 3

  1. Importante.  Critique a seguinte ideia: para transformar um vetor em heap, basta rearranjá-lo em ordem decrescente (usando o algoritmo Mergesort ou o algoritmo Quicksort, por exemplo).
  2. Prove que a função constroiHeap está correta. Comece por estabelecer os invariantes do processo iterativo nas linhas 5 a 7.
  3. Discuta a seguinte versão da função constroiHeap:
       int k; 
       for (k = 1; k < m; ++k) {                   
          int f = k+1, x = v[k+1];
          while (f > 1 && v[f/2] < x) { 
             v[f] = v[f/2];
             f /= 2; }
          v[f] = x; }
    

A função peneira

O coração de muitos algoritmos que manipulam heaps é uma função que, ao contrário de constroiHeapdesce em direção à base da árvore.  Essa função, que chamaremos peneira, recebe um vetor qualquer v[1..m] e
faz v[1] descer até sua posição correta,
pulando de uma camada para a seguinte.  Como isso é feito?  Se v[1] ≥ v[2] e v[1] ≥ v[3], não é preciso fazer nada.  Se v[1] < v[2] e v[2] ≥ v[3], basta trocar v[1] com v[2] e depois fazer v[2] descer para sua posição correta.  Os dois outros casos são semelhantes.   (Faça um rascunho do algoritmo em pseudocódigo.)   No exemplo a seguir, cada linha retrata o estado do vetor no início de uma iteração:
8599989796959493929190899786
9985989796959493929190899786
9997988596959493929190899786
9997989396959485929190899786
Segue o código da função.  Cada iteração começa com um índice p e escolhe o filho f de p que tem maior valor:
static void 
peneira (int m, int v[]) {
   int f = 2;
   while (f <= m) {
      if (f < m && v[f] < v[f+1])  ++f;
      // f é o filho mais valioso de f/2
      if (v[f/2] >= v[f]) break;
      troca (v[f/2], v[f]);
      f *= 2;
   }
}
A função será aplicada a vetores que são heaps exceto talvez por um ou dois índices.  A função pode, portanto, ser documentada assim:
// Recebe um vetor v[1..m] que é um heap
// exceto talvez pelos índices 2 e 3 e
// rearranja o vetor de modo a
// transformá-lo em heap.
A seguinte versão é um pouco melhor, porque faz menos movimentações de elementos do vetor (e menos divisões de f por 2):
static void
peneira (int m, int v[])
{ 
   int p = 1, f = 2, t = v[1];
   while (f <= m) {
      if (f < m && v[f] < v[f+1])  ++f;
      if (t >= v[f]) break;
      v[p] = v[f];
      p = f, f = 2*p;
   }
   v[p] = t;
}
Desempenho.   A função peneira é muito rápida. Ela faz no máximo  lg(m)  iterações, uma vez que o vetor tem 1 + lg(m) camadas.  Cada iteração envolve duas comparações entre elementos do vetor e portanto o número total de comparações não passa de
2 lg(m) .
O consumo de tempo é proporcional ao número de comparações e portanto proporcional a  log m  no pior caso.

Exercícios 4

  1. Por que a seguinte implementação de peneira não funciona?
        int p = 1, f = 2;
        while (f <= m) {
           if (v[p] < v[f]) {
              troca (v[p], v[f]);
              p = f;
              f = 2*p; }
           else {
              if (f < m && v[p] < v[f+1]) {
                 troca (v[p], v[f+1]);
                 p = f+1;
                 f = 2*p; }
              else break; } }
    
  2. O seguinte código alternativo da função peneira funciona corretamente?
       int p = 1, f;                        
       for (f = 2; f <= m; f *= 2) {
          if (f < m && v[f] < v[f+1])  ++f;
          p = f/2;
          if (v[p] >= v[f]) break;
          troca (v[p], v[f]); }
    
  3. Discuta a seguinte variante do código de peneira:
       int x = v[1], f = 2;
       while (f <= m) {
          if (f < m && v[f] < v[f+1])  ++f;
          if (x >= v[f]) break;
          v[f/2] = v[f];
          f *= 2;
       }
       v[f/2] = x;
    
  4. Escreva uma versão recursiva da função peneira.
  5. Peneira generalizada.  Suponha que um vetor v[1..m] é um heap exceto talvez pelos índices 2p e 2p+1. Escreva uma função peneira_2 que receba v[1..m] e p e transforme o vetor em heap. (Basta generalizar o código de peneira.)
  6. Construção rápida de um heap.   Mostre que a seguinte função tem o mesmo efeito que constroiHeap acima, ou seja, transforma qualquer vetor v[1..m] em heap:
    void constroiHeap_2 (int m, int v[]) {
       for (p = m/2; p >= 1; --p)  
          peneira_2 (p, m, v);
    }
    
    (Veja peneira_2 no exercício anterior.)  Mostre que constroiHeap_2 faz no máximo (m lg(m))/2 comparações entre elementos do vetor.  Refine sua análise para mostrar que a função não faz mais que  m  comparações.
  7. O seguinte fragmento de código transforma qualquer vetor v[1..m] em heap?
    for (p = 1; p <= m/2; ++p)  
       peneira_2 (p, m, v);
    
  8. Fila de prioridades.  Uma fila de prioridades (= priority queue) é um conjunto de objetos (números, por exemplo) sujeito a duas operações:  (1) remoção de um elemento de valor máximo e (2) inserção de um novo elemento.  Se o conjunto for mantido num heap, essas duas operações podem ser realizadas de maneira muito rápida. Implemente as duas operações de modo que cada uma consuma tempo proporcional a log n no pior caso, sendo n o número de objetos no conjunto.

O algoritmo Heapsort

Não é difícil reunir o que dissemos acima para obter um algoritmo que rearranja um vetor v[1..n] em ordem crescente.  O algoritmo tem duas fases: a primeira transforma o vetor em heap e a segunda rearranja o heap em ordem crescente. (Comece fazendo um rascunho do algoritmo.)
// Rearranja os elementos do vetor v[1..n] 
// de modo que fiquem em ordem crescente.

void
heapsort (int n, int v[])
{
   int m;
   constroiHeap (n, v);
   for (m = n; m >= 2; --m) {
      troca (v[1], v[m]);
      peneira (m-1, v);
   }
}
No início de cada iteração valem as seguintes propriedades (invariantes):
  • o vetor v[1..m] é um heap,
  • v[1..m] ≤ v[m+1..n] ,
  • v[m+1..n] está em ordem crescente e
  • v[1..n] é uma permutação do vetor original.
É claro que v[1..n] estará em ordem crescente quando m for igual a 1.
1heapmcrescenten
888777666555444333222111000999999999999999
elementos pequenoselementos grandes

Animações do Heapsort

Exercícios 5

  1. Use a função heapsort para ordenar o vetor  16 15 14 13 12 11 10 9 8 7 6 5 4 .  Mostre o estado do vetor no início de cada iteração.
  2. Descreva o estado do vetor no início de uma iteração genérica do algoritmo Heapsort.
  3. A função heapsort produz um rearranjo estável do vetor, ou seja, preserva a ordem relativa de elementos de mesmo valor?
  4. Escreva uma função com protótipo  heap_sort (int *v, int n)  que rearranje um vetor v[0..n-1] em ordem crescente. (Basta invocar heapsort da maneira correta.)
  5. Testes com vetor aleatório.  Escreva um programa que teste, experimentalmente, a correção de sua implementação do algoritmo Heapsort. Use permutações aleatórias de 1..n para os testes. Compare o resultado com 1..n.
  6. Min-Heap.  Escreva uma função que rearranje um vetor v[1..n] em ordem decrescente.  Sugestão: Adapte a definição de heap e reescreva a função peneira.
  7. Imite um heap por meio de um conjunto de células interligadas com ponteiros. Cada célula terá quatro campos: 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 apropriada da função peneira.  (Veja o capítulo Árvores binárias.)

Desempenho do Heapsort

Quantas comparações entre elementos do vetor a função heapsort executa?  A função auxiliar constroiHeap faz  n lg(n)  comparações no máximo.  Em seguida, a função peneira é chamada cerca de n vezes e cada uma dessas chamadas faz  2 lg(n)  comparações no máximo.  Logo, o número total de comparações não passa de
3 n lg(n) .
Quanto ao consumo de tempo do heapsort, ele é proporcional ao número de comparações entre elementos do vetor, e portanto proporcional a
n log n
no pior caso.

Exercícios 6

  1. Cronometragem.  Escreva um programa que cronometre sua implementação do Heapsort (use a função clock da biblioteca time).  Divida os tempos por n log n para comparar com a previsão teórica.
[Curso de AeED - Aula 06] [Algoritmo] Ordenação - Heapsort [Curso de AeED - Aula 06] [Algoritmo] Ordenação - Heapsort Reviewed by Vinicius dos Santos on 10:32:00 Rating: 5

Nenhum comentário

Escreve ai sua opinião!