Ordenação: HeapSort - DECOM- ?· HeapSort • Algoritmo: 1. Construir o heap. 2. Troque o item na…

  • Published on
    26-Jan-2019

  • View
    212

  • Download
    0

Embed Size (px)

Transcript

<p>Ordenao: HeapSortProf. Tlio Toffolohttp://www.toffolo.com.br</p> <p>BCC202 Aula 17Algoritmos e Estruturas de Dados I</p> <p>2014-01 Aula 16 Fila de Prioridade / HeapSortAdaptado por Reinaldo Fortes para o curso de 2014-01Arquivo original: Aula 17: HeapSort</p> <p>FILAS DE PRIORIDADE</p> <p>Fila de Prioridade</p> <p> uma estrutura de dados onde a chave de cada item reflete sua habilidade relativa de abandonar o conjunto de itens rapidamente.</p> <p> Aplicaes: SOs usam filas de prioridades, nas quais as chaves </p> <p>representam o tempo em que eventos devem ocorrer. Mtodos numricos iterativos so baseados na </p> <p>seleo repetida de um item com maior (menor) valor. Sistemas de gerncia de memria usam a tcnica de </p> <p>substituir a pgina menos utilizada na memria principal por uma nova pgina.</p> <p>3</p> <p>TAD - Fila de Prioridade</p> <p> Operaes:1. Constri uma fila de prioridades a partir de um </p> <p>conjunto com n itens.2. Informa qual o maior item do conjunto.3. Retira o item com maior chave.4. Insere um novo item.5. Aumenta o valor da chave do item i para um novo </p> <p>valor que maior que o valor atual da chave.</p> <p>4</p> <p>OBS: Neste ponto, estamos considerando que item com maior chave tem maior prioridade.</p> <p>TAD - Fila de Prioridade</p> <p> Operaes:6. Substitui o maior item por um novo item, a no ser </p> <p>que o novo item seja maior.7. Altera a prioridade de um item.8. Remove um item qualquer.9. Agrupar duas filas de prioridades em uma nica.</p> <p>5</p> <p>OBS: Neste ponto, estamos considerando que item com maior chave tem maior prioridade.</p> <p>Filas de Prioridades - Representao</p> <p> Lista linear ordenada: Constri O(n log n) ou O(n2). Insere O(n). Retira O(1). Altera O(n).</p> <p> Lista linear no ordenada: Constri O(n). Insere O(1). Retira O(n). Altera O(n)</p> <p>6</p> <p>FILA DE PRIORIDADE:</p> <p>HEAP</p> <p>Heap</p> <p> A melhor representao de uma fila de prioridade atravs de uma estrutura de dados chamada heap: Neste caso, Constri O(n). Insere, Retira, Substitui e Altera so O(log n).</p> <p> Observao: Para implementar a operao Agrupar de forma </p> <p>eficiente e ainda preservar um custo logartmico para as operaes Insere, Retira, Substitui e Altera necessrio utilizar estruturas de dados mais sofisticadas, tais como rvores binomiais (Vuillemin, 1978).</p> <p>8</p> <p>Heap</p> <p> uma rvore binria em que um n filho sempre maior ou igual a um n pai.</p> <p> Ou seja: chave(v) &gt;= chave(pai(v))</p> <p>9</p> <p>2</p> <p>65</p> <p>79 n raiz (menor elemento)</p> <p>Heap</p> <p> rvore binria completa: Os ns so numerados de 0 a n-1. O primeiro n chamado raiz. O n (k-1)/2 o pai do n k, para 0 &lt; k &lt; n. Os ns 2k+1 e 2k+2 so os filhos esquerda e </p> <p>direita do n k, para 0 &lt; k </p> <p>Heap</p> <p> Cada n possui uma tupla (chave, elemento) Assim, cada n do heap armazena todo o item sendo </p> <p>armazenado</p> <p>11</p> <p>(2, Sue)</p> <p>(6, Mark)(5, Pat)(9, Jeff)</p> <p>(7, Anna)</p> <p>Heaps</p> <p> As chaves na rvore satisfazem condio do heap.</p> <p> A chave em cada n menor do que as chaves em seus filhos.</p> <p> A chave no n raiz a menor chave do conjunto. Uma rvore binria completa pode ser </p> <p>representada por um array:</p> <p>12</p> <p>0 1 2 3 4 5 6</p> <p>2 5 6 9 7 8 10</p> <p>Heaps</p> <p> A representao extremamente compacta. Permite caminhar pelos ns da rvore facilmente.</p> <p> Os filhos de um n i esto nas posies: 2i+1 e 2i+2. O pai de um n i est na posio (i-1) div 2.</p> <p> Na representao do heap em um arranjo, a menor (ou maior) chave est sempre na posio 0 do vetor. Heap mnimo: menor elemento na raiz. Heap mximo: maior elemento na raiz.</p> <p>13</p> <p>HEAPOPERAES</p> <p>Construo do Heap</p> <p> Um algoritmo elegante para construir o heap foi proposto por Floyd em 1964.</p> <p> O algoritmo no necessita de nenhuma memria auxiliar.</p> <p> Dado um vetor A[0], A[1], ..., A[n-1]: Os itens A[n/2], A[n/2 + 1], ..., A[n-1] formam um </p> <p>heap vlido pois so ns folhas (ns que no possuem filhos).</p> <p> Neste intervalo no existem dois ndices i e j tais que j = 2i+1 ou j = 2i+2.</p> <p>15</p> <p>Construo do Heap</p> <p>16</p> <p>0 1 2 3 4 5 6</p> <p>9 5 6 8 3 2 7</p> <p>9 5 2 8 3 6 7</p> <p>9 3 2 8 5 6 7</p> <p>2 3 9 8 5 6 7</p> <p>2 3 6 8 5 9 7</p> <p>Vetor inicial</p> <p>Esq = 2</p> <p>Esq = 1</p> <p>Esq = 0</p> <p>Esq = 0</p> <p>Construo do Heap</p> <p> Os itens de A[3] a A[6] formam um heap. O heap estendido para a esquerda (Esq = 2), </p> <p>englobando o item A[2], pai dos itens A[5] e A[6]. A condio de heap violada:</p> <p> O heap refeito trocando os itens A[2] e A[5]. O item 5 (A[1]) incluindo no heap (Esq = 1) A condio de heap violada:</p> <p> O heap refeito trocando os itens A[1] e A[4].</p> <p>17</p> <p>Construo do Heap</p> <p> O item 9 (A[0]) incluindo no heap (Esq = 0) A condio de heap violada:</p> <p> O heap refeito trocando os itens A[0] e A[1]. Como a condio ainda est sendo violada:</p> <p> O heap refeito trocando os itens A[1] e A[4].</p> <p> Como resultado, o heap foi construdo: 2 3 6 8 5 9 7</p> <p>18</p> <p>Inserir um N no Heap</p> <p>19</p> <p>2</p> <p>65</p> <p>79</p> <p>N sendo inserido</p> <p>2</p> <p>65</p> <p>79 1</p> <p>z</p> <p>z</p> <p>Comparar o n inserido com os pais e trocar enquantoele for menor que o pai ouat que ele seja o n raiz</p> <p>Inserir um N no Heap</p> <p> Na pior das hipteses o custo de uma insero ser O(n log n), equivalente altura da rvore</p> <p>20</p> <p>1</p> <p>25</p> <p>79 6z</p> <p>2</p> <p>15</p> <p>79 6z</p> <p>Remover um N do Heap</p> <p>21</p> <p>Trocar o n raiz pelo ltimo n do heap eremover o ltimo n</p> <p>2</p> <p>65</p> <p>79</p> <p>ltimo N</p> <p>w</p> <p>7</p> <p>65</p> <p>9w</p> <p>novo ltimo N</p> <p>Remover um N do Heap</p> <p> Refazer o heap! Na pior das hipteses o custo de uma remoo </p> <p>ser O(n log n), equivalente altura da rvore</p> <p>22</p> <p>7</p> <p>65</p> <p>9</p> <p>w 5</p> <p>67</p> <p>9</p> <p>w</p> <p>ORDENAO USANDO HEAP</p> <p>HEAPSORT</p> <p>Ordenao usando Filas de Prioridades</p> <p> As operaes das filas de prioridades podem ser utilizadas para implementar algoritmos de ordenao.</p> <p> Basta utilizar repetidamente a operao Insere para construir a fila de prioridades.</p> <p> Em seguida, utilizar repetidamente a operao Retira para receber os itens na ordem correta.</p> <p> O uso de heap para fazer a ordenao origina o mtodo HeapSort.</p> <p>24</p> <p>Heapsort</p> <p> Para reduzir o nmero de operaes, ser utilizado um Heap em que o maior valor armazenado na raiz Teremos que o valor de um n pai dever ser sempre </p> <p>maior ou igual aos valores dos seus filhos</p> <p> Utilizaremos repetidamente a operao Insere para construir a fila de prioridades.</p> <p> Em seguida, utilizaremos repetidamente a operao Retira para receber os itens na ordem inversa.</p> <p>25</p> <p>HeapSort</p> <p> Algoritmo:1. Construir o heap.</p> <p>2. Troque o item na posio 1 do vetor (raiz do heap) com o item da posio n-1.</p> <p>3. Use o procedimento Refaz para reconstituir o heap para os itens A[0], A[1], ..., A[n - 2].</p> <p>4. Repita os passos 2 e 3 com os n - 1 itens restantes, depois com os n - 2, at que reste apenas um item.</p> <p>26</p> <p>HeapSort</p> <p> Exemplo de aplicao do Heapsort: Link para o arquivo.</p> <p>27</p> <p>http://www.decom.ufop.br/reinaldo/site_media/uploads/2013-02-bcc202/exemploheapsort.png</p> <p>HEAPSORTIMPLEMENTAO</p> <p>void heapRefaz(TItem *v, int esq, int dir) { int i = esq; int j = i*2 + 1; // j = prim eiro filho de i TItem aux = v[i]; // aux = no i (pai de j) w hile (j &lt; = dir) { if (j &lt; dir &amp;&amp; v[j].chave &lt; v[j+ 1].chave) j+ + ; // j recebe o outro filho de i if (aux.chave &gt; = v[j].chave) break; // heap foi refeito corretam ente v[i] = v[j]; i = j; j = i*2 + 1; // j = prim eiro filho de i } v[i] = aux;}</p> <p>HeapSort</p> <p>29</p> <p>void heapConstroi(TItem *v, int n) { int esq; esq = (n / 2) 1; // esq = n anterior ao prim eiro n folha do heap w hile (esq &gt; = 0) { heapRefaz(v, esq, n-1); esq--; }}</p> <p>HeapSort</p> <p>30</p> <p>void heapSort(TItem *v, int n) { TItem aux; heapConstroi(v, n); w hile (n &gt; 1) { aux = v[n-1]; v[n-1] = v[0]; v[0] = aux; n--; heapRefaz(v, 0, n-1); // refaz o heap }}</p> <p>HeapSort</p> <p>31</p> <p>MERGESORTANLISE DO ALGORITMO</p> <p>Heapsort</p> <p> O procedimento Refaz gasta cerca de log n operaes, no pior caso.</p> <p> Constroi executa O(n) x Refaz Loop interno executa O(n) x Refaz Logo, Heapsort gasta um tempo de execuo O(n </p> <p>log n) no pior caso.</p> <p>33</p> <p>Anlise do HeapSort</p> <p> A altura h da rvore de execuo O(log n) Refazer o heap, na pior das hipteses, tem custo </p> <p>igual altura da rvore. Construir o heap custa O(n log n)</p> <p> Logo: algoritmo O(n log n)</p> <p>34</p> <p>h = O(log n)</p> <p>MERGESORTVANTAGENS/DESVANTAGENS</p> <p>Quando usar o Heapsort?</p> <p> O HeapSort recomendado: Para aplicaes que no podem tolerar eventualmente </p> <p>um caso desfavorvel. No recomendado para arquivos com poucos </p> <p>registros, por causa do tempo necessrio para construir o heap.</p> <p>36</p> <p>Heapsort</p> <p> Vantagens: O comportamento do Heapsort sempre O(n log n), </p> <p>qualquer que seja a entrada. Desvantagens:</p> <p> O anel interno do algoritmo bastante complexo se comparado com o do Quicksort.</p> <p> O Heapsort no estvel.</p> <p>37</p> <p>Perguntas?</p> <p>38</p> <p>HEAPSORT</p> <p>EXERCCIO</p> <p>Exerccio</p> <p> Dada a sequncia de nmeros:</p> <p>3 4 9 2 5 1 8Ordene em ordem crescente utilizando o algoritmo HeapSort, apresentado a sequncia dos nmeros e explicando cada passo do algoritmo.</p> <p>40</p> <p>Slide 1Slide 2Fila de PrioridadeTAD - Fila de PrioridadeTAD - Fila de PrioridadeFilas de Prioridades - RepresentaoSlide 7HeapHeapHeapHeapHeapsHeapsSlide 14Construo do HeapConstruo do HeapConstruo do HeapConstruo do HeapInserir um N no HeapInserir um N no HeapRemover um N do HeapRemover um N do HeapSlide 23Ordenao usando Filas de PrioridadesHeapsortHeapSortHeapSortSlide 28HeapSortHeapSortHeapSortSlide 32HeapsortAnlise do HeapSortSlide 35Quando usar o Heapsort?HeapsortSlide 38Slide 39Exerccio</p>

Recommended

View more >