Análise de Algoritmos - Aula 09 (Guilherme)

Prévia do material em texto

Ana´lise de
Algoritmos
113859
Aula 9
Roteiro
Heaps
Heapsort
Exerc´ıcios
Roteiro da Aula 9
1 Heaps
Heapify
Construindo um heap
2 Heapsort
3 Exerc´ıcios
Ana´lise de
Algoritmos
113859
Aula 9
Roteiro
Heaps
Heapify
Construindo um
heap
Heapsort
Exerc´ıcios
Heaps
1 Um heap e´ uma a´rvore bina´ria quase completa, onde os
no´s possuem um valor; e que satisfaz:
2 Propriedade do heap de ma´ximo: o valor de qualquer no´ e´
maior ou igual que o valor dos seus filhos;
14 10
8 7 9 3
2 4 1
16
8 9
4 5 6 7
32
16
1
10
Ana´lise de
Algoritmos
113859
Aula 9
Roteiro
Heaps
Heapify
Construindo um
heap
Heapsort
Exerc´ıcios
Heaps
1 Um heap e´ uma a´rvore bina´ria quase completa, onde os
no´s possuem um valor; e que satisfaz:
2 Propriedade do heap de ma´ximo: o valor de qualquer no´ e´
maior ou igual que o valor dos seus filhos;
14 10
8 7 9 3
2 4 1
16
8 9
4 5 6 7
32
16
1
10
1 2 3 4 5 6 7 8 9 10
16 14 10 8 7 9 3 2 4 1
Ana´lise de
Algoritmos
113859
Aula 9
Roteiro
Heaps
Heapify
Construindo um
heap
Heapsort
Exerc´ıcios
Representac¸a˜o impl´ıcita para Heaps
1 2 3 4 5 6 7 8 9 10
16 14 10 8 7 9 3 2 4 1
int pai( int i ){
return floor(i/2);
}
int esq( int i ){
return 2*i;
}
int dir( int i ){
return (2*i)+1;
}
Ana´lise de
Algoritmos
113859
Aula 9
Roteiro
Heaps
Heapify
Construindo um
heap
Heapsort
Exerc´ıcios
Heaps
Qual e´ a altura de um heap com n elementos?
14 10
8 7 9 3
2 4 1
16
8 9
4 5 6 7
32
16
1
10
Ana´lise de
Algoritmos
113859
Aula 9
Roteiro
Heaps
Heapify
Construindo um
heap
Heapsort
Exerc´ıcios
Heaps
Qual e´ a altura de um heap com n elementos?
⌊logn⌋
14 10
8 7 9 3
2 4 1
16
8 9
4 5 6 7
32
16
1
10
Ana´lise de
Algoritmos
113859
Aula 9
Roteiro
Heaps
Heapify
Construindo um
heap
Heapsort
Exerc´ıcios
Heapify
• Entrada: Um vetor A e um ı´ndice i; tal que
as a´rvores com raiz em esq(i) e dir(i) sa˜o heaps;
10
7 9 3
2 1
16
8 9
4 5 6 7
32
16
1
10
8
14
4
i
• Sa´ıda: a a´rvore com raiz em i deve ser um heap;
Ana´lise de
Algoritmos
113859
Aula 9
Roteiro
Heaps
Heapify
Construindo um
heap
Heapsort
Exerc´ıcios
Heapify
Por induc¸a˜o...
heapify( int* A, int i ){
int maior; int l=esq(i); int r=dir(i);
if ((l <= heapsize)&&(A[l] > A[i])) maior = l;
else maior = i;
if ((r <= heapsize)&&(A[r] > A[maior])) maior = r;
if ( maior != i ){
swap( &A[i], &A[maior] );
heapify( A, maior );
}
}
Qual e´ o custo de heapify?
Ana´lise de
Algoritmos
113859
Aula 9
Roteiro
Heaps
Heapify
Construindo um
heap
Heapsort
Exerc´ıcios
Construindo um heap
1 2 3 4 5 6 7 8 9 10
4 1 3 2 16 9 10 14 8 7
Ana´lise de
Algoritmos
113859
Aula 9
Roteiro
Heaps
Heapify
Construindo um
heap
Heapsort
Exerc´ıcios
Construindo um heap
1 2 3 4 5 6 7 8 9 10
4 1 3 2 16 9 10 14 8 7
build-heap( int* A, int n ){
/* n e´ o tamanho do vetor A */
heapsize = n;
for( i = floor(n/2); i >= 1; i-- ) heapify( A, i );
}
Ana´lise de
Algoritmos
113859
Aula 9
Roteiro
Heaps
Heapify
Construindo um
heap
Heapsort
Exerc´ıcios
Construindo um heap
Quanto custa build-heap( A, n )?
Ana´lise de
Algoritmos
113859
Aula 9
Roteiro
Heaps
Heapify
Construindo um
heap
Heapsort
Exerc´ıcios
Construindo um heap
Quanto custa build-heap( A, n )?
• heapify( A , i ) realiza, no pior caso, 2h
comparac¸o˜es, onde h e´ a altura do no´ i;
Ana´lise de
Algoritmos
113859
Aula 9
Roteiro
Heaps
Heapify
Construindo um
heap
Heapsort
Exerc´ıcios
Construindo um heap
Quanto custa build-heap( A, n )?
• heapify( A , i ) realiza, no pior caso, 2h
comparac¸o˜es, onde h e´ a altura do no´ i;
• Portanto, o custo sera´ proporcional a` soma das alturas de
todos os no´s, Soma(h); para uma a´rvore completa...
Ana´lise de
Algoritmos
113859
Aula 9
Roteiro
Heaps
Heapify
Construindo um
heap
Heapsort
Exerc´ıcios
Construindo um heap
Quanto custa build-heap( A, n )?
• heapify( A , i ) realiza, no pior caso, 2h
comparac¸o˜es, onde h e´ a altura do no´ i;
• Portanto, o custo sera´ proporcional a` soma das alturas de
todos os no´s, Soma(h); para uma a´rvore completa...
Soma(h) = 2Soma(h − 1) + h
Ana´lise de
Algoritmos
113859
Aula 9
Roteiro
Heaps
Heapify
Construindo um
heap
Heapsort
Exerc´ıcios
Construindo um heap
Quanto custa build-heap( A, n )?
• heapify( A , i ) realiza, no pior caso, 2h
comparac¸o˜es, onde h e´ a altura do no´ i;
• Portanto, o custo sera´ proporcional a` soma das alturas de
todos os no´s, Soma(h); para uma a´rvore completa...
Soma(h) = 2Soma(h − 1) + h
Soma(h) = Θ(2h)
Ana´lise de
Algoritmos
113859
Aula 9
Roteiro
Heaps
Heapify
Construindo um
heap
Heapsort
Exerc´ıcios
Construindo um heap
• Mas, n, o nu´mero de no´s de uma a´rvore completa,
tambe´m e´ Θ(2h)!
• Portanto, build-heap( A, n ) custa Θ(n).
Ana´lise de
Algoritmos
113859
Aula 9
Roteiro
Heaps
Heapsort
Exerc´ıcios
Heapsort
Construir e desconstruir um heap...
heapsort( int* A, int n ){
build-heap( A, n );
for( i = n; i >= 2; i-- ){
swap( &A[1], &A[i] );
heapsize--;
heapify( A, i );
}
}
Quanto custa heapsort( A, n )?
heapsort ordena in-place?
Ana´lise de
Algoritmos
113859
Aula 9
Roteiro
Heaps
Heapsort
Exerc´ıcios
Heapsort
Construir e desconstruir um heap...
heapsort( int* A, int n ){
build-heap( A, n );
for( i = n; i >= 2; i-- ){
swap( &A[1], &A[i] );
heapsize--;
heapify( A, i );
}
}
Quanto custa heapsort( A, n )?
heapsort ordena in-place?
Θ(n logn)
Sim
Ana´lise de
Algoritmos
113859
Aula 9
Roteiro
Heaps
Heapsort
Exerc´ıcios
Exerc´ıcios
1 O vetor abaixo e´ um heap de ma´ximo?
[23, 17, 14, 6, 13, 10, 1, 5, 7, 12]
2 Em quais posic¸o˜es o menor elemento pode estar em um heap de
ma´ximo?
3 O heapsort e´ esta´vel?
4 Use induc¸a˜o (substituic¸a˜o) para mostrar que S(h) = O(2n), para
S(h) = 2S(h− 1) + h;
5 Mostre como realizar o merge de k vetores de tamanho n em tempo
o(k2n);
6 Considere vetores de n inteiros onde ha´ apenas O(log n) valores
diferentes; quer dizer, ha´ muitos elementos repetidos. Projete um
algoritmo para realizar a ordenac¸a˜o desse vetor em tempo
O(n log log n). Por que isso na˜o contradiz a cota inferior Ω(n logn)?
Dicas para 5 e 6: como extrair o ma´ximo de um heap e atualiza´-lo? Como
inserir um elemento em um heap?
	Roteiro
	Heaps
	Heapify
	Construindo um heap
	Heapsort
	Exercícios