Buscar

Fila de prioridade e HeapSort

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 3, do total de 40 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 6, do total de 40 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 9, do total de 40 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

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

Outros materiais