Heapsort

Esta página examina um algoritmo sofisticado que rearranja um vetor dado em ordem crescente. Para que a descrição do algoritmo fique mais simples, convém 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  ["Algorithm 232 (heapsort)", Communications of the ACM, 7, p.347-348, 1964].

Veja o verbete Heapsort na Wikipedia.  Veja também o capítulo 14 do "Programming Pearls".

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  ⌊f/2⌋ ,  ou seja, o piso de f/2, isto é, 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

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

• o índice 1 é a raiz da árvore;
• o pai de um índice f é f/2 (é claro que 1 não tem pai);
• o filho esquerdo de um índice p é 2p e o filho direito é 2p+1  (é claro que o filho esquerdo só existe se 2p ≤ m e o filho direito só existe se 2p+1 ≤ m).

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

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

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 ideia é óbvia. Se v[p] ≥ v[2p] e v[p] ≥ v[2p+1] então não é preciso fazer nada. Se v[p] < v[2p] e 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 no terceiro caso.

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 função iterativa que faz o serviç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 raízes são filhos
// de p já são max-heaps.

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

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

void peneira( int p, int m, int v[])
{ 
   int f = 2*p, x = v[p];
   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;
}

A função peneira: desempenho

A função peneira é muito rápida. O consumo de tempo é proporcional ao número de iterações, e esse numero não passa de

log₂m

pois o valor de f pelo menos dobra a cada iteração.

Exercícios

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 lg(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 lg(m))/2, pois o tempo gasto em cada uma das m/2 iterações é limitado por lg(m).  É um pouco mais difícil verificar que o tempo é, na verdade, limitado por m apenas.)

Exercícios

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 os seguinte invariantes:

• o vetor v[1..n] é uma permutação do vetor original,
• o vetor v[1..m] é um max-heap,
  
• v[1..m]  ≤  v[m+1..n] e
  
• o vetor v[m+1..n] está em ordem crescente.

É claro que v[1..n] estará em ordem crescente quando m for igual a 1.

1	max-heap							m		crescente			n
888	777	666	555	444	333	222	111	000	999	999	999	999	999
elementos pequenos									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 log₂n ,

mesmo no pior caso. De fato, o primeiro for constrói o max-heap inicial e faz no máximo  n lg(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 lg(n)  comparações entre elementos do vetor.

Heapsort: animações

Veja applets de animação do algoritmo:

• Sorting Algorithms Animation by David R. Martin
• Sorting Algorithms na Universidade de British Columbia
• Sorting Algorithms, página de Pat Morin na Universidade de Carlton, Canadá

Exercícios

Uma versão mais rápida do Heapsort

A seguinte versão do Heapsort, um pouco diferente da examinada acima, é conhecida com Bottom-Up-Heapsort:

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

void bottom_up_heapsort( int n, int v[])
{
   int m, f, max, t;
   constroi_heap( n, v);
   for (m = n; m > 1; --m) {
      max = v[1];
      f = 2;
      while (f <= m) {
         if (f < m && v[f] < v[f+1]) ++f;
         v[f/2] = v[f];
         f *= 2;
      }
      f = f/2;
      if (f < m) {
         t = v[f], v[f] = v[m], v[m] = t;
         while (f > 1 && v[f/2] < v[f]) { 
            t = v[f], v[f] = v[f/2], v[f/2] = t;
            f = f/2;
         }
      }
      v[m] = max;
   }
}

No começo de cada iteração do for, o vetor v[1..m] é um heap que contém os elementos pequenos e o vetor v[m+1..n] é crescente e contém os elementos grandes.

// Recebe um vetor v[1..n] e transforma o vetor em 
// um max-heap

void constroi_heap( int n, int v[])
{
   int m, f, t;
   for (m = 1; m < n; ++m) {
      f = m+1;
      while (f > 1 && v[f/2] < v[f]) { 
         t = v[f/2], v[f/2] = v[f], v[f] = t;
         f = f/2;
      }
   }
}

No início de cada iteração do for, o vetor v[1..m] é um heap.   No começo de cada iteração do while, todos os índices em 1..m+1 satisfazem a propriedade do max-heap exceto talvez v[f] grande demais para v[f/2].

I. Wegener e J. Stolfi observaram que esta versão Heapsort faz, em média, duas vezes menos comparações entre elementos do vetor que a versão discutida acima. (Mas isso não significa, necessariamente, que ela seja duas vezes mais rápida se levarmos em conta as outras operações, como as trocas, por exemplo.

Exercício