Ordenação: Heapsort Algoritmos e Estruturas de Dados II

  • Published on
    18-Apr-2015

  • View
    105

  • Download
    2

Embed Size (px)

Transcript

<ul><li> Slide 1 </li> <li> Ordenao: Heapsort Algoritmos e Estruturas de Dados II </li> <li> Slide 2 </li> <li> Introduo 2 Possui o mesmo princpio de funcionamento da ordenao por seleo. Selecione o menor item do vetor Troque-o pelo item da primeira posio Repita operao com os elementos restantes do vetor Implementao direta Encontrar o menor elemento requer n-1 comparaes Ideia: Utilizao de uma fila de prioridades implementada com um heap. </li> <li> Slide 3 </li> <li> Fila de Prioridades 3 Definio: Estrutura de dados composta de chaves, que suporta duas operaes bsicas: insero de um novo item e remoo do item com a maior chave. A chave de cada item reflete a prioridade em que se deve tratar aquele item. Aplicaes: Sistemas operacionais, sistema de memria (paginao). </li> <li> Slide 4 </li> <li> Fila de Prioridades 4 Operaes Constri a fila de prioridade com N itens Insere um novo item Retira o maior item Altera a prioridade de um item </li> <li> Slide 5 </li> <li> Fila de Prioridades 5 Representaes Lista sequencial ordenada, no ordenada e heap. ConstriInsereRetira mximoAltera prioridade Lista ordenada O(N log N)O(N)O(1)O(N) Lista no ordenada O(N)O(1)O(N)O(1) heaps O(N log N)O(log N) </li> <li> Slide 6 </li> <li> Fila de Prioridades 6 Algoritmos de ordenao com fila de prioridades Utiliza operao insere para adicionar todas as N chaves Utiliza a operao retira mximo para receber uma lista na ordem reversa. Algoritmo Lista ordenada Lista no ordenada heaps </li> <li> Slide 7 </li> <li> Fila de Prioridades 7 Algoritmos de ordenao com fila de prioridades Utiliza operao insere para adicionar todas as N chaves Utiliza a operao retira mximo para receber uma lista na ordem reversa. Algoritmo Lista ordenada Insero Lista no ordenada Seleo heaps Heapsort </li> <li> Slide 8 </li> <li> Heap 8 Representao vetorial A[1], A[2],..., A[n] A[i] A[2i] A[i] A[2i+1] i = 1, 2, 3,..., n/2. Representao em rvore binria Ser um heap se cada n for maior ou igual seus filhos. </li> <li> Slide 9 </li> <li> Heap 9 Representao em rvore binria Ns so numerados de 1 a n O primeiro chamado raiz O n k/2 o pai do n k, 1 &lt; k n Os ns 2k e 2k+1 so filhos da esquerda e direita do n k, para 1 k n/2. </li> <li> Slide 10 </li> <li> Heap 10 rvores binria pode ser representadas por vetores. Uma representao muito compacta Permite caminhar pelos ns da rvore facilmente Filhos de um n i esto nas posies 2i e 2i + 1 O pai de um n i est na posio i/2 </li> <li> Slide 11 </li> <li> Heap 11 Construindo/Restaurao da condio de heap. Garantir que o valor da chave do pai maior que dos filhos. Observe que os ns n/2,..., n satisfazem a condio, uma vez que no tem filhos. Para todo i de n/2 at 1 Troque o n com seu filho de maior chave, at que nenhuma mudana ocorra. </li> <li> Slide 12 </li> <li> Heap 12 Restaurao da condio de heap (rvore) DROENAS 1234567 D RO ENAS 1 2 3 6547 D RO ENAS 1 2 3 6547 D RS ENAO 1 2 3 6547 1 2 3 S RD ENAO 1 2 3 6547 4 </li> <li> Slide 13 </li> <li> Heap Refaz a condio de heap 13 void RefazCimaBaixo(Item A[], int k, int Dir) { int j; while (2*k </li> <li> Heap Construo do heap 14 void Constroi(Item A[], int N) { int Esq; /* inicia na metade do vetor */ Esq = N / 2 + 1; while (Esq &gt; 1) { Esq--; RefazCimaBaixo(A, Esq, N); } </li> <li> Slide 15 </li> <li> Heap Refaz a condio de heap 15 void RefazBaixoCima(Item A[], int k) { /* se pai for menor que filho, troca */ while (k &gt; 1 &amp;&amp; A[k/2] &lt; A[k]) { Troca(A[k], A[k/2]); /* vai para o pai e repete o processo */ k = k / 2; } </li> <li> Slide 16 </li> <li> Heap Operaes 16 Int N; /* controla nmero de elementos na fila */ Item pq[MaxN]; /* contm os dados */ /* inicia fila de prioridade */ Void FPInicia() { N = 0; } /* insere um elemento */ void FPInsere(Item v) { A[++N] = v; RefazBaixoCima(pq, N); } /* remove elemento com valor mximo */ Item FPRemoveMaximo() { Troca(pq[1], pq[N]); RefazCimaBaixo(pq, 1, N-1); return pq[N--]; } </li> <li> Slide 17 </li> <li> Heapsort Ordenao com fila de prioridades 17 Void FPSort(Item A[], int n) { int k; FPInicia(); /* insere elementos na fila de prioridade */ for (k = 0; k &lt; n; k++) FPInsere(A[k]); /* remove maiores elementos da fila de prioridade */ for (k = n-1; k &gt;= 0; k--) a[k] = FPRemoveMaximo(); } </li> <li> Slide 18 </li> <li> Heapsort Anlise Algoritmos e Estrutura de Dados II O procedimento RefazCimaBaixo gasta cerca de log n operaes no pior caso. Logo, o heapsort gasta um tempo proporcional a O(n log n), no pior caso. </li> <li> Slide 19 </li> <li> Heapsort 19 Vantagens O(n log n). Desvantagens No estvel. </li> <li> Slide 20 </li> <li> Exerccios 20 1. Por que no usar o algoritmo de ordenao por seleo para identificar o k-simo menor elemento do vetor? 2. Mesmo com o uso da estratgia da mediana, mostre um vetor de entrada que cai no pior caso do quicksort. 3. Um vetor com elementos em ordem reversa um heap? 4. Mostre que o heapsort no estvel. </li> </ul>