Aula sobre Heapsort

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

jan/2003
katia@cin.ufpe.br
*
katia@cin.ufpe.br
*
Heapsort
Katia S. Guimarães
katia@cin.ufpe.br
katia@cin.ufpe.br
jan/2003
katia@cin.ufpe.br
*
katia@cin.ufpe.br
*
Recordando a construção de um Heap
Algoritmo Constrói-Heap:
	 Para i  n/2 até 1 faça 
		Heapify (A, n, i )
Onde:
 A é o array contendo os elementos
 n é o número de elementos no array, e
 i é o índice do nó raiz da sub-árvore 
 considerada.
katia@cin.ufpe.br
jan/2003
katia@cin.ufpe.br
*
katia@cin.ufpe.br
*
Algoritmo Heapify
Algoritmo Heapify(A, n, i )
 Enquanto 2i  n /* i tem filhos*/ faça 
 { Se 2i < n /* i tem dois filhos*/
 então Se A[2i ] > A[2i +1]
 		 então maior  2i 
 senão maior  2i +1
 senão /* o único é o maior*/ maior  2i ;
 Se A[i ] < A[maior] então
 então {A[i ]  A[maior]; i  maior } 
 senão i  n /* deixe o laço*/ 
 }
katia@cin.ufpe.br
jan/2003
katia@cin.ufpe.br
*
katia@cin.ufpe.br
*
Heapsort
Após construir o heap, o array é visto como
contendo: um heap + parte da solução
 9
21
22
26
34
41
74
74
22
41
21
9
34
26
 9
21
26
74
22
34
41
74
22
41
21
9
34
26

41
22
34
21
9
26
74
katia@cin.ufpe.br
jan/2003
katia@cin.ufpe.br
*
katia@cin.ufpe.br
*
Heapsort
 9
21
26
74
41
22
34

41
26
34
21
9
22
74
 9
21
26
74
22
34
41
41
26
34
21
9
22
74
41
26
34
21
9
22
74
katia@cin.ufpe.br
jan/2003
katia@cin.ufpe.br
*
katia@cin.ufpe.br
*
Heapsort
34
 9
21
74
41
22
26

41
21
26
9
34
22
74
 9
21
26
74
41
22
34
41
26
34
21
9
22
74
41
26
34
21
9
22
74
katia@cin.ufpe.br
jan/2003
katia@cin.ufpe.br
*
katia@cin.ufpe.br
*
Heapsort
34
26
21
74
41
 9
22

41
21
22
26
34
9
74
34
 9
21
74
41
22
26
41
21
26
9
34
22
74
41
21
26
9
34
22
74
katia@cin.ufpe.br
jan/2003
katia@cin.ufpe.br
*
katia@cin.ufpe.br
*
Heapsort
34
26
 9
74
41
22
21

41
9
21
26
34
22
74
34
26
21
74
41
 9
22
41
21
22
26
34
9
74
41
21
22
26
34
9
74
katia@cin.ufpe.br
jan/2003
katia@cin.ufpe.br
*
katia@cin.ufpe.br
*
Heapsort
34
26
21
74
41
22
 9

41
21
9
26
34
22
74
34
26
 9
74
41
22
21
41
9
21
26
34
22
74
41
9
21
26
34
22
74
katia@cin.ufpe.br
jan/2003
katia@cin.ufpe.br
*
katia@cin.ufpe.br
*
Heapsort
Algoritmo Heapsort (A, n)
	Constrói-Heap(A, n) 
	Para j  n até 2 faça 
	 {	exchange (A[1], A[ j]); 
		Heapify (A, j, 1) }
katia@cin.ufpe.br
jan/2003
katia@cin.ufpe.br
*
katia@cin.ufpe.br
*
Custo do Heapsort
 T(n) = Custo (Constrói-Heap) + Custo (laço)
katia@cin.ufpe.br
jan/2003
katia@cin.ufpe.br
*
katia@cin.ufpe.br
*
Relembrando o custo para construir um Heap bottom-up
Qual é a soma das alturas de todas as sub-árvores 
dentro de uma árvore de altura h ? 
h = 0 0 
h = 1 1 
 h = 2  4 
katia@cin.ufpe.br
jan/2003
katia@cin.ufpe.br
*
katia@cin.ufpe.br
*
Relembrando o custo para construir um Heap bottom-up
A soma das alturas de todas as sub-árvores 
dentro de uma árvore de altura h é dada por: 
 H(h) = 2 · H(h-1) + h H(0) = 0
 h 0 1 2 3 4 5 6 7 ... 
H(h) 0 1 4 11 26 57 120 247 ...
 2h+1 2 4 8 16 32 64 128 256 ...
 H(h) = 2h+1 - (h+2) =  (n) 
katia@cin.ufpe.br
jan/2003
katia@cin.ufpe.br
*
katia@cin.ufpe.br
*
Custo do Laço
O laço é executado exatamente n-1 vezes.
A cada iteração, ocorre 
 - Uma troca de elementos no array
 (tempo constante) 
 - Heapify (tempo proporcional à 
 altura da árvore, que é logarítmico)
Logo, Custo (laço) =  (n · log (n) ) 
katia@cin.ufpe.br
jan/2003
katia@cin.ufpe.br
*
katia@cin.ufpe.br
*
Custo do Heapsort
 T(n) = Custo (Constrói-Heap) + Custo (laço)
 T(n) = [ (n)] + [n · log2 (n)] = 
 =  (n · log (n) ) 
OBS: 
 A constante do Heapsort é menor que a do 
 MergeSort. Por quê?
katia@cin.ufpe.br
jan/2003
katia@cin.ufpe.br
*
katia@cin.ufpe.br
*
Constantes do Heapsort vs. MergeSort
 1. A cada comparação, o MergeSort realiza uma movimentação de dados, enquanto que o Heapsort nem sempre faz isso.
 2. Além disso, o MergeSort sempre faz as 
 n • log n comparações, enquanto o 
 HeapSort pode encerrar a reorganização do heap sem precisar descer até uma folha.
katia@cin.ufpe.br
jan/2003
katia@cin.ufpe.br
*
katia@cin.ufpe.br
*
Heapsort
OBSERVAÇÕES: 
O algoritmo Heapsort tem um número de comparações 
 de chaves no pior caso comparável ao do MergeSort. 
 Mas como ele faz muito menos cópias de chaves, ele
 é consideravelmente mais rápido.
2. Em termos de espaço, o Heapsort é um algoritmo 
 in-place, enquanto o MergeSort necessita do dobro 
 do espaço necessário para as chaves.
katia@cin.ufpe.br
jan/2003
katia@cin.ufpe.br
*
katia@cin.ufpe.br
*
Para que serve o MergeSort? 
Se o algoritmo Heapsort é melhor que o MergeSort em 
tempo de execução em em espaço, para que serve o MS?
O MergeSort tem duas características muito interessantes: 
 - Localidade de referências (a cada chamada recursiva, 
 as comparações vão-se fazendo entre elementos cada 
 vez mais próximos), e 
 - Blocos de tamanho controlável. 
katia@cin.ufpe.br
jan/2003
katia@cin.ufpe.br
*
katia@cin.ufpe.br
*
Para que serve o MergeSort? 
Essas duas características são muito úteis quando se está 
ordenando um arquivo muito grande, que precisa ser 
mantido em dispositivo externo. 
A localidade de referências diminui o número de acessos a
dispositivos externos (o “gargalo” neste tipo de aplicação),
 e permite o controle no tamanho dos blocos de dados a 
serem lidos.
katia@cin.ufpe.br