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