Projeto de Algoritmos  |  Linguagem C  |  Índice  |  English

Heapsort

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:

• o índice 1 é a raiz da árvore;
• o pai de qualquer índice  f  é  f/2  (é claro que 1 não tem pai);
• o filho esquerdo de um índice  p  é  2p  (esse filho só existe se 2p ≤ m );
• o 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 calculadas em aritmética inteira. Assim, uma expressão da forma f/2 significa  ⌊f/2⌋ , ou seja, o piso de f/2.

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.

Exercícios 1

Heap

O segredo do algoritmo Heapsort é uma estrutura de dados, conhecida como heap, que enxerga o vetor como uma árvore 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 exatamente, 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⌋ .)

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

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 exatamente, 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

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

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

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

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

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

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

A animação à direita (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:

• Heapsort, na Wikipedia.
• Heapsort animation, de David Galles (University of San Francisco).
• Animação de 15 algoritmos de ordenação, de Timo Bingmann, no YouTube.
• Sorting Algorithms Animations da Toptal.

Exercícios 5

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