Heapsort

[pile-of-sand-7283847_orig.png]

[Heapsort-github.gif]

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 descoberto por J.W.J. Williams em 1964. O Heapsort linearítmico, mesmo no pior caso.

Suporemos que os índices do vetor são  1 . . n  e não 0 . . n−1 (como é usual em C) pois essa convenção torna o código um pouco mais simples.

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.  O conjunto de índices de qualquer vetor  v[1..m]  pode ser encarado como uma árvore binária da seguinte maneira:

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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14
999 999 999 999 999 999 999 999 999 999 999 999 999 999

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
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 56

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; trataremos aqui apenas do primeiro, omitindo o prefixo max.

Um heap (= monte) é um vetor em que o valor de todo pai é maior ou igual ao valor de cada um de seus dois filhos. Mais precisamente, um vetor v[1..m] é um heap se

v[f/2] ≥ v[f]

para f = 2, . . . , m .  (Como já dissemos acima, a expressão f/2 deve ser entendida como ⌊f/2⌋.)

1 2 3 4 5 6 7 8 9 10 11 12 13 14
999 888 777 555 666 777 555 222 333 444 111 333 666 333

Para entender o algoritmo 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 os elementos um vetor de inteiros 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, enquanto 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[])
{
   for (int 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 que não deve 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 camada 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 ser mais eficiente e transformar v[1..m] em heap com apenas m comparações.)

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 57.
  3. Discuta a seguinte versão da função constroiHeap:
       for (int 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 constroiHeap, desce 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:

85 99 98 97 96 95 94 93 92 91 90 89 97 86
 
99 85 98 97 96 95 94 93 92 91 90 89 97 86
 
99 97 98 85 96 95 94 93 92 91 90 89 97 86
 
99 97 98 93 96 95 94 85 92 91 90 89 97 86

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, x = v[1];
   while (f <= m) {
      if (f < m && v[f] < v[f+1]) ++f;
      if (x >= v[f]) break;
      v[p] = v[f];
      p = f, f = 2*p;
   }
   v[p] = x;
}

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 está correto?
       for (int f = 2; f <= m; f *= 2) {
          if (f < m && v[f] < v[f+1]) ++f;
          int 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 2p2p+1. Escreva uma função peneira_2 que receba v[1..m]p e transforme o vetor em heap.
  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 (int 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, na verdade, a função faz no máximo  m  comparações.

  7. O seguinte fragmento de código transforma qualquer vetor v[1..m] em heap?
    for (int 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[])
{
   constroiHeap (n, v);
   for (int m = n; m >= 2; --m) {
      troca (v[1], v[m]);
      peneira (m-1, v);
   }
}

No início de cada iteração do for {} valem as seguintes propriedades (invariantes):

A expressão  v[1..m] ≤ v[m+1..n]  é uma abreviatura de  todos os elementos de v[1..m] são menores ou iguais a todos os elementos de v[m+1..n].

1 heap m crescente n
888 777 666 555 444 333 222 111 000 999 999 999 999 999
elementos pequenos elementos grandes

Segue daí que v[1..n] estará em ordem crescente quando m for igual a 1.  Portanto, o algoritmo está correto.

Animações do Heapsort

[Heapsort-github.gif]

A animação à esquerda (copiada de Simon Waldherr / Golang Sorting Visualization) mostra a aplicação do Heapsort a um vetor v[0..79] de números positivos. Cada elemento v[i] do vetor é representado pelo ponto de coordenadas (i,v[i]).  (Por algum motivo, a animação não executa as duas últimas iterações.)

Veja outras animações de algoritmos de ordenação:

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] (note os índices) 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 e compare o vetor ordenado 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 apontando o pai da célula, outro apontando o filho direito, e outro apontando 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.  (Entretanto, a constante de proporcionalidade é maior que a do Mergesort e a do Quicksort.)

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.