Baixe o app para aproveitar ainda mais
Prévia do material em texto
Ordenação: HeapSort Prof. Túlio Toffolo http://www.toffolo.com.br BCC202 – Aula 17 Algoritmos e Estruturas de Dados I 2014-01 – Aula 16 – Fila de Prioridade / HeapSort Adaptado por Reinaldo Fortes para o curso de 2014-01 Arquivo original: Aula 17 - HeapSort FILAS DE PRIORIDADE Fila de Prioridade • É uma estrutura de dados onde a chave de cada item reflete sua habilidade relativa de abandonar o conjunto de itens rapidamente. • Aplicações: • SOs usam filas de prioridades, nas quais as chaves representam o tempo em que eventos devem ocorrer. • Métodos numéricos iterativos são baseados na seleção repetida de um item com maior (menor) valor. • Sistemas de gerência de memória usam a técnica de substituir a página menos utilizada na memória principal por uma nova página. 3 TAD - Fila de Prioridade • Operações: 1. Constrói uma fila de prioridades a partir de um 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 valor que é maior que o valor atual da chave. 4 OBS: Neste ponto, estamos considerando que item com maior chave tem maior prioridade. TAD - Fila de Prioridade • Operações: 6. Substitui o maior item por um novo item, a não ser 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. 5 OBS: Neste ponto, estamos considerando que item com maior chave tem maior prioridade. Filas de Prioridades - Representação • Lista linear ordenada: • Constrói é O(n log n) ou O(n2). • Insere é O(n). • Retira é O(1). • Altera é O(n). • Lista linear não ordenada: • Constrói é O(n). • Insere é O(1). • Retira é O(n). • Altera é O(n) 6 FILA DE PRIORIDADE: HEAP Heap • A melhor representação de uma fila de prioridade é através de uma estrutura de dados chamada heap: • Neste caso, Constrói é O(n). • Insere, Retira, Substitui e Altera são O(log n). • Observação: • Para implementar a operação Agrupar de forma eficiente e ainda preservar um custo logarítmico para as operações Insere, Retira, Substitui e Altera é necessário utilizar estruturas de dados mais sofisticadas, tais como árvores binomiais (Vuillemin, 1978). 8 Heap • É uma árvore binária em que um nó filho é sempre maior ou igual a um nó pai. • Ou seja: chave(v) >= chave(pai(v)) 9 2 6 5 7 9 nó raiz (menor elemento) Heap • Árvore binária completa: • Os nós são numerados de 0 a n-1. • O primeiro nó é chamado raiz. • O nó (k-1)/2 é o pai do nó k, para 0 < k < n. • Os nós 2k+1 e 2k+2 são os filhos à esquerda e à direita do nó k, para 0 < k <= n/2 (mais detalhes a seguir). 10 Heap • Cada nó possui uma tupla (chave, elemento) • Assim, cada nó do heap armazena todo o item sendo armazenado 11 (2, Sue) (6, Mark) (5, Pat) (9, Jeff) (7, Anna) Heaps • As chaves na árvore satisfazem à condição do heap. • A chave em cada nó é menor do que as chaves em seus filhos. • A chave no nó raiz é a menor chave do conjunto. • Uma árvore binária completa pode ser representada por um array: 12 0 1 2 3 4 5 6 2 5 6 9 7 8 10 Heaps • A representação é extremamente compacta. • Permite caminhar pelos nós da árvore facilmente. • Os filhos de um nó i estão nas posições: 2i+1 e 2i+2. • O pai de um nó i está na posição (i-1) div 2. • Na representação do heap em um arranjo, a menor (ou maior) chave está sempre na posição 0 do vetor. • Heap mínimo: menor elemento na raiz. • Heap máximo: maior elemento na raiz. 13 HEAP OPERAÇÕES Construção do Heap • Um algoritmo elegante para construir o heap foi proposto por Floyd em 1964. • O algoritmo não necessita de nenhuma memória auxiliar. • Dado um vetor A[0], A[1], ..., A[n-1]: • Os itens A[n/2], A[n/2 + 1], ..., A[n-1] formam um heap válido pois são nós folhas (nós que não possuem filhos). • Neste intervalo não existem dois índices i e j tais que j = 2i+1 ou j = 2i+2. 15 Construção do Heap 16 0 1 2 3 4 5 6 9 5 6 8 3 2 7 9 5 2 8 3 6 7 9 3 2 8 5 6 7 2 3 9 8 5 6 7 2 3 6 8 5 9 7 Vetor inicial Esq = 2 Esq = 1 Esq = 0 Esq = 0 Construção do Heap • Os itens de A[3] a A[6] formam um heap. • O heap é estendido para a esquerda (Esq = 2), englobando o item A[2], pai dos itens A[5] e A[6]. • A condição de heap é violada: • O heap é refeito trocando os itens A[2] e A[5]. • O item 5 (A[1]) é incluindo no heap (Esq = 1) • A condição de heap é violada: • O heap é refeito trocando os itens A[1] e A[4]. 17 Construção do Heap • O item 9 (A[0]) é incluindo no heap (Esq = 0) • A condição de heap é violada: • O heap é refeito trocando os itens A[0] e A[1]. • Como a condição ainda está sendo violada: • O heap é refeito trocando os itens A[1] e A[4]. • Como resultado, o heap foi construído: • 2 3 6 8 5 9 7 18 Inserir um Nó no Heap 19 2 6 5 7 9 Nó sendo inserido 2 6 5 7 9 1 z z Comparar o nó inserido com os pais e trocar enquanto ele for menor que o pai ou até que ele seja o nó raiz Inserir um Nó no Heap • Na pior das hipóteses o custo de uma inserção será O(n log n), equivalente à altura da árvore 20 1 2 5 7 9 6 z 2 1 5 7 9 6 z Remover um Nó do Heap 21 Trocar o nó raiz pelo último nó do heap e remover o último nó 2 6 5 7 9 último Nó w 7 6 5 9 w novo último Nó Remover um Nó do Heap • Refazer o heap! • Na pior das hipóteses o custo de uma remoção será O(n log n), equivalente à altura da árvore 22 7 6 5 9 w 5 6 7 9 w ORDENAÇÃO USANDO HEAP HEAPSORT Ordenação usando Filas de Prioridades • As operações das filas de prioridades podem ser utilizadas para implementar algoritmos de ordenação. • Basta utilizar repetidamente a operação Insere para construir a fila de prioridades. • Em seguida, utilizar repetidamente a operação Retira para receber os itens na ordem correta. • O uso de heap para fazer a ordenação origina o método HeapSort. 24 Heapsort • Para reduzir o número de operações, será utilizado um Heap em que o maior valor é armazenado na raiz • Teremos que o valor de um nó pai deverá ser sempre maior ou igual aos valores dos seus filhos • Utilizaremos repetidamente a operação Insere para construir a fila de prioridades. • Em seguida, utilizaremos repetidamente a operação Retira para receber os itens na ordem inversa. 25 HeapSort • Algoritmo: 1. Construir o heap. 2. Troque o item na posição 1 do vetor (raiz do heap) com o item da posição n-1. 3. Use o procedimento Refaz para reconstituir o heap para os itens A[0], A[1], ..., A[n - 2]. 4. Repita os passos 2 e 3 com os n - 1 itens restantes, depois com os n - 2, até que reste apenas um item. 26 HeapSort • Exemplo de aplicação do Heapsort: • Link para o arquivo. 27 HEAPSORT IMPLEMENTAÇÃO void heapRefaz(TItem *v, int esq, int dir) { int i = esq; int j = i*2 + 1; // j = primeiro filho de i TItem aux = v[i]; // aux = no i (pai de j) while (j <= dir) { if (j < dir&& v[j].chave < v[j+1].chave) j++; // j recebe o outro filho de i if (aux.chave >= v[j].chave) break; // heap foi refeito corretamente v[i] = v[j]; i = j; j = i*2 + 1; // j = primeiro filho de i } v[i] = aux; } HeapSort 29 void heapConstroi(TItem *v, int n) { int esq; esq = (n / 2) – 1; // esq = nó anterior ao primeiro nó folha do heap while (esq >= 0) { heapRefaz(v, esq, n-1); esq--; } } HeapSort 30 void heapSort(TItem *v, int n) { TItem aux; heapConstroi(v, n); while (n > 1) { aux = v[n-1]; v[n-1] = v[0]; v[0] = aux; n--; heapRefaz(v, 0, n-1); // refaz o heap } } HeapSort 31 MERGESORT ANÁLISE DO ALGORITMO Heapsort • O procedimento Refaz gasta cerca de log n operações, no pior caso. • Constroi – executa O(n) x Refaz • Loop interno – executa O(n) x Refaz • Logo, Heapsort gasta um tempo de execução O(n log n) no pior caso. 33 Análise do HeapSort • A altura h da árvore de execução é O(log n) • Refazer o heap, na pior das hipóteses, tem custo igual à altura da árvore. Construir o heap custa O(n log n) • Logo: algoritmo é O(n log n) 34 h = O(log n) MERGESORT VANTAGENS/DESVANTAGENS Quando usar o Heapsort? • O HeapSort é recomendado: • Para aplicações que não podem tolerar eventualmente um caso desfavorável. • Não é recomendado para arquivos com poucos registros, por causa do tempo necessário para construir o heap. 36 Heapsort • Vantagens: • O comportamento do Heapsort é sempre O(n log n), qualquer que seja a entrada. • Desvantagens: • O anel interno do algoritmo é bastante complexo se comparado com o do Quicksort. • O Heapsort não é estável. 37 Perguntas? 38 HEAPSORT EXERCÍCIO Exercício • Dada a sequência de números: 3 4 9 2 5 1 8 Ordene em ordem crescente utilizando o algoritmo HeapSort, apresentado a sequência dos números e explicando cada passo do algoritmo. 40
Compartilhar