Heapsort

Disponível somente no TrabalhosFeitos
  • Páginas : 8 (1787 palavras )
  • Download(s) : 0
  • Publicado : 31 de maio de 2012
Ler documento completo
Amostra do texto
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 quetenhamos 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 é umvetor 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 |
Estranha 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 longeestá 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]).
A função peneira
O coração de qualquer algoritmo que manipule ummax-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 noterceiro 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 |...
tracking img