Universidade Federal de Ouro Preto Departamento de Computação · 2017. 3. 29. · Fila de...

Universidade Federal de Ouro PretoDepartamento de Computação

Prof. Haroldo Gambini Santos

Fila de Prioridades

2

Fila de Prioridade: Aplicações

Em muitas aplicações queremos saber quais o(s) primeiro(s) elementos de uma ordenaçãoEm um algoritmo de roteamento, por exemplo, podemos considerar visitar somente as cidades que se encontram até uma certa distância

3

Fila de Prioridade: Aplicações

No processamento de eventos em um sistema operacional algumas tarefas são mais importantes que outrasNovas tarefas podem surgir a qualquer momento e serão processadas de acordo com a sua prioridade

http://www.freertos.org

4

Fila de Prioridade: Aplicações

Simulação:Eventos são gerados – eventos que ocorrem primeiro devem se processados antes e podem gerar novos eventos

http://en.wikipedia.org/wiki/Computer_simulation

5

TAD : Fila de Prioridade

Operações básicas em uma fila de prioridade QCria( Q );Insere( Q, (k,x) )

insere em Q o elemento x com prioridade k

(k,x) = Retira( Q )remove o item mais prioritário de Q

Operações que podem ser desejáveis em Q Cria( Q , {x1,x2...} )

Altera( Q, x, k )Modifica a prioridade do item x para k

Remove( Q, x )Remove item x

6

Fila de Prioridade

Implementação computacional mantendo um vetor não ordenado, custo:

Insere ( Q, (k,x) ) ?(k,x) = Retira( Q ) ?

7

Custo

Vetor não Ordenado

Vetor Ordenado

Árvore Balanceada

Insere ( Q, (k,x) ) O(1) O(n) O( log n )

(k,x) = Retira( Q ) O(n) O(1) O( log n )

8

Heap Binária

Uma heap binária é uma árvore binária completai.e.: todos os níveis exceto o último estão preenchidos Desse modo, altura máxima log n

http://interactivepython.org/runestone/static/pythonds/Trees/heap.html

5

9 11

14 18 19 21

33 17 27

9

Árvore Binária Completa: Representação por Vetor

0 5 9 11 14 18 19 21 33 17 27

0 1 2 3 4 5 6 7 8 9 10 11

5

9 11

14 18 19 21

33 17 27

2p

p

2p+12p

2p+1

⌊p/2⌋

⌊p/2⌋

⌊p/2⌋

⌊p/2⌋

10

Propriedade de Ordem da Heap

Pai n1 para filho n2 : n1 ≤ n2

Irmãos não são ordenados

5

9 11

14 18 19 21

33 17 27

11

Operação de Inserção

5

9 11

14 18 19 21

33 17 27 7

7

18

9

7

adiciona-se o elemento na última posição do vetor (nível mais baixo da árvore)inicia-se a operação de subida até que a propriedade de ordem da heap seja satisfeita

12

Remoção do Item Mais Prioritário

5

9 11

18 19 21

33 17 27

279

2714

271417

27

troca-se o elemento de maior prioridade (raiz da árvore, posição 1 do vetor) pelo elemento da última posição do vetorenquanto ordenação da heap não satisfeita realizar descida trocando sempre pelo filho de menor valor

13

Construção

Implementação de Cria( Q , {x1,x2...} )

Possibilidade:Criar Q vazia e chamar repetidamente Insere( Q, (k,x) )Cada chamada de Insere : O( log n )

O( n log n )Pode-se fazer melhor ?

14

Construção

100 20 90 60 50 120 140 130

110701030

150

4080

Entrada

50 80 40 10 70 110 30 120 140 60 50 130 100 20 90

Folhas são heaps válidasFolhas são heaps válidas

Nós internos devem ser verificados e corrigidos

Nós internos devem ser verificados e corrigidos

50

7030

20 80

10

15

Construção

function buildHeap( {x1,x2,...,xn} )v[] = { 0, x1,x2,...,xn };i = ⌊n/2⌋;while (i>0)

down( v, i );--i;

return v;

16

Questões adicionais

Heaps não permitem a busca rápida de um elemento qualquerEm algumas aplicações as prioridades mudam

Soluções ?