aed9

Amontoados e Filas de Prioridade

Fac. Cincias Univ. Lisboa Luis Antunes Algoritmos e Estruturas de Dados

Hoje

! Filas com prioridade.

! Amontoados. ! Implementao com um ArrayList. ! Algoritmos de insero e remoo.

Fac. Cincias Univ. Lisboa

Luis Antunes Algoritmos e Estruturas de Dados

Filas com prioridade

! Servem para filas que no seguem a lei FIFO, por exemplo uma fila de impreso.

! Uma fila com prioridade uma fila na qual apenas o item com maior prioridade est acessvel

! Durante a insero, a posio do item na fila baseada na sua prioridade em relao s prioridades dos outros itens da lista



PriorityQueue ! boolean offer (E item)

! Insere item na fila, devolve true se tem sucesso, false se no pode ser inserido

! E remove() ! Remove a entrada mais pequena e devolve-a, se a fila no est vazia.

Se est d uma excepo

! E poll() ! Remove e devolve a entrada mais pequena, vazia --> null

! E peek() ! Devolve a entrada mais pequena sem a remover. Vazia --> null

! E element() ! Devolve a entrada mais pequena sem a remover. Vazia --> excepo



Amontoados (Heaps)

! Um amontoado uma rvore binria diferente de uma rvore binria de procura:

! Em cada nvel da rvore, o valor do n menor do que todos os valores das suas duas sub-rvores

! Formalmente: ! Um Heap uma rvore binria completa na qual

! O valor da raz o item mais pequeno da rvore ! Todas as sub-rvores so Heaps



Exemplo de Heap



6

18

20

29

28 39 66

37 26 76 32 74

Insero num Heap

! Insere-se o item na prxima posio livre, no fundo

! Enquanto o novo item no estiver na raiz e for menor que o seu pai ! Troca-se o novo item com o seu pai

! Exemplo: inserir 8



6

18

20

29

28 39 66

37 26 76 32 74 89 8

6

18

20

29

28 39 8

37 26 76 32 74 89 66

6

18

20

8

28 39 29

37 26 76 32 74 89 66

Remoo dum Heap

! Remove-se a raiz e substitui-se pelo ltimo item do heap

! Enquanto o UIH tem filhos e maior que algum deles ! Troca-se o UIH com o seu filho mais pequeno

! No ex, depois de tirar o 6:



66

18

20 28 39 29

37 26 76 32 74 89

8

8

18

20 28 39 29

37 26 76 32 74 89

66

8

18

20 28 39 66

37 26 76 32 74 89

29

Implementao do Heap

! Como o Heap uma rvore binria completa, podemos implement-lo eficientemente usando um array (ou ArrayList), assim: ! A raiz fica no primeiro elemento (ndice 0) ! Os dois elementos seguintes (1 e 2) guardam os dois filhos da

raiz ! Os elementos 3, 4, 5 e 6 guardam os 4 netos da raiz ! Etc

! O Heap uma sequncia de filas, com cada fila medindo o dobro da anterior.

! Todas as filas esto cheias excepto a ltima



Exemplo da representao



6

18

20 28 39 66

37 26 76 32 74 89

29

6 18 29 20 28 39 66 37 26 76 32 74 89

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

Em geral

! Um n na posio p ! tem o seu filho esquerdo na posio 2p+1 ! tem o seu filho esquerdo na posio 2p+2

! Um n na posio c ! tem o seu pai em (c1)/2

! Usamos o ArrayList porque mais fcil de expandir e contrair do que um array



Insero num Heap

! Inserir o novo elemento no fim do array ! e seja child = table.size()1

! Seja parent = (child1)/2

! Enquanto (parent >=0 && table[parent] > table[child]) ! Trocar table[parent] com table[child] ! Seja child = parent ! Seja parent = (child1)/2



Remoo dum Heap ! Remover e guardar o elemento do topo table[0]

! Remover o ltimo elemento table[size()1] ! e coloc-lo na posio 0

! Seja parent = 0

! Enquanto (true) ! Seja leftChild= (2*parent)+1 e rightChild = leftChild+1 ! Se leftChild >= table.size() sair do loop ! Assumimos que minChild = leftChild ! Se rightChild < table.size() e table[rightChild] table[minChild]

! Trocar table[parent] com table[minChild] ! Seja parent = minChild

! C.c: sair do loop Fac. Cincias

Univ. Lisboa Luis Antunes Algoritmos e Estruturas de Dados

sadas

O item desceu tanto que j no tem filhos

Ou mais pequeno que os seus dois filhos

Exemplo remoo



Performance de um Heap

! Remover usa um caminho da raiz at uma folha, e inserir usa um caminho da folha at raiz, o que requer h passos, com h a altura da rvore

! A rvore tem 2(h1) ns

! Logo, tanto inserir como o remover tm performance:

! O(log n)



Documents

aed9