Filas de Prioridade

Filas de Prioridade
Em algumas situações, é necessário manter um
conjunto dinâmico de chaves, tal que a principal
Notas de aula da disciplina IME 04-10820 operação no conjunto é a retirada do elemento de
ESTRUTURAS DE DADOS I maior prioridade (chave). A manutenção do con-
junto ordenado é uma solução para o problema,
Paulo Eustáquio Duarte Pinto mas o uso das filas de prioridade fornece uma
(pauloedp arroba [Link]) solução mais simples. Ex: seleção de jobs.
Filas de prioridade são estruturas de dados para
as quais se tem operações eficientes para:

-Seleção do elemento de maior prioridade - (1)

junho/2017 -Inserção/deleção de elementos - (log n)
-Mudanças de prioridade - (log n)

Filas de Prioridade Filas de Prioridade

Heaps Heaps
Um Heap é um vetor que pode ser visto como uma árvore
Heaps implementam filas de prioridade. Um Heap binária (virtual!). A raiz é a célula 1 e os filhos do nó i
é uma árvore binária (virtual!), onde a chave de estão nas células 2i e 2i+1, se existirem.
cada nó é  () que a dos descendentes. 1 2 3 4 5 6 7 8 9 10
Exemplo:
50 28 17 18 3 17 1 1 17 2
Exemplo:
50 50

28 17 28 1
17
2 3
18 3 17 1 18 3 17 1
4 5 6 7
1 17 2 1 17 2
8
9 10

Filas de Prioridade Filas de Prioridade

Heaps Heaps
Inserção de um novo elemento no Heap. Inserção de um novo elemento no Heap.
Solução: inserir no final e executar SOBEHEAP. Solução: inserir no final e executar SOBEHEAP.
1 2 3 4 5 6 7 8 9 10 11 1 2 3 4 5 6 7 8 9 10 11
Exemplo: Exemplo:
50 28 17 18 3 17 1 1 17 2 29 50 29 17 18 28 17 1 1 17 2 3

50 50

29 28 1
17 29 1
17

18
2
3 29 17
28 3
1 18
2
28 17
3
1
4 5 6 7 4 5 6 7
1 17 2 29 3 1 17 2 3
8 8
9 10 11 9 10 11

1
 Filas de Prioridade Filas de Prioridade

Heaps Heaps
Inserção de um novo elemento no Heap -
Criação de um Heap a partir de um vetor já pre-
enchido, usando SOBEHEAP.
SOBEHEAP.

SobeHeap(k): CriaHeap:
#Dados: Vetor V com n elementos, k inteiro #Dados: Vetor V com n elementos

t  V[k]; V[0]  t; Para i de 2 a n:

SobeHeap(i);
Enquanto (V[k/2] < t):
V[k]  V[k/2]; Fim;
k  k/2;

V[k]  t;
Fim;
Complexidade: O(n log n)
Complexidade: O(log n)

Filas de Prioridade Filas de Prioridade

Heaps Heaps
Criação de um Heap a partir de um vetor já pre- Criação de um Heap a partir de um vetor já pre-
enchido, usando SOBEHEAP. enchido, usando SOBEHEAP.
1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10
Exemplo: Exemplo:
1 28 17 18 2 17 1 17 50 3 28 18 17 1 2 17 1 17 50 3

28
1 28 28
18 17
28 1 1 17
1
18 2 17 1
17

Filas de Prioridade Filas de Prioridade

Heaps Heaps
Criação de um Heap a partir de um vetor já pre- Criação de um Heap a partir de um vetor já pre-
enchido, usando SOBEHEAP. enchido, usando SOBEHEAP.
1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10
Exemplo: Exemplo:
28 18 17 17 2 17 1 1 50 3 50 28 17 18 2 17 1 1 17 3
28 50

18 17 28 17

17 2 17 1 18 2 17 1

1 50 1 17 3

2
 Filas de Prioridade Filas de Prioridade

Heaps Heaps
Criação de um Heap a partir de um vetor já pre- Criação de um Heap a partir de um vetor já pre-
enchido, usando SOBEHEAP. enchido, usando SOBEHEAP.
1 2 3 4 5 6 7 8 9 10
Exemplo:
50 28 17 18 3 17 1 1 17 2
Exercício: Criar um Heap a partir do vetor
50 preenchido com o MIXTRING (10 letras)
usando SobeHeap
28 17

18 3 17 1

1 17 2

Filas de Prioridade Filas de Prioridade

Heaps Heaps
Deleção do elemento de maior prioridade no Heap.
Complexidade da criação de um Heap a partir de Solução: substituir o primeiro pelo último, eliminar no final
um vetor já preenchido, usando SOBEHEAP. e executar DESCEHEAP.
1 2 3 4 5 6 7 8 9 10
Exemplo:
NC = 1  i  (h -1) i.2i = 1  i  (h -1) i  j  (h -1) 2j 50 28 17 18 3 17 1 1 17 2
=  1  i  (h -1) (0  j  (h -1) 2 -  0  j  (i -1) 2 )
j j
2 50 2
=  1  i  (h -1) (2 -1 - (2 - 1))
h i

= 2 1  i  (h -1) 1 - 1  i  (h -1) 2
h i

28 1
17
=2
h(h - 1) - (2h - 2) = 2h(h - 2) +2
2 3
Quando (n + 1) é potência de 2, temos 2h = (n + 1) 18 3 17 1
4 5 6 7
NC = (n + 1)(log2(n+1) - 2) + 2 = (n + 1)log2(n+1) - 2n 1
= O(n log n)
17 2
8 9 10

Filas de Prioridade Filas de Prioridade

Heaps Heaps
Deleção do elemento de maior prioridade no Heap. Deleção do elemento de maior prioridade no Heap.
Solução: substituir o primeiro pelo último, eliminar no final Solução: substituir o primeiro pelo último, eliminar no final
e executar DESCEHEAP. e executar DESCEHEAP.
1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9
Exemplo: Exemplo:
2 28 17 18 3 17 1 1 17 28 2 17 18 3 17 1 1 17
2 28
28 1
17 2 1
17
2 3
18 3 17 1 18
2
3 17
3
1
4 5 6 7 7
1 17 1
4
17
5 6

8 9 8 9

3
 Filas de Prioridade Filas de Prioridade

Heaps Heaps
Deleção do elemento de maior prioridade no Heap. Deleção do elemento de maior prioridade no Heap.
Solução: substituir o primeiro pelo último, eliminar no final Solução: substituir o primeiro pelo último, eliminar no final
e executar DESCEHEAP. e executar DESCEHEAP.
1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9
Exemplo: Exemplo:
28 18 17 2 3 17 1 1 17 28 18 17 17 3 17 1 1 2

28 28
18 1
17 18 1
17
2 3 2 3
2 3 17 1 17 3 17 1
4 5 6 7 4 5 6 7
1 17 1 2
8 9 8 9

Filas de Prioridade Filas de Prioridade

Heaps Heaps
Diminuição da prioridade de um elemento-
DESCEHEAP. Criação de um Heap a partir de um vetor já pre-
enchido, usando DESCEHEAP.
DesceHeap(k, m):
#Dados: Vetor V com m elementos, k inteiro
t  V[k]; CriaHeap:
#Dados: Vetor V com n elementos
Enquanto (k  m/2): Para i decrescendo de n/2 até 1:
j  2*k; DesceHeap(i, n);
Se (j < m) e (V[j] < V[j+1]) Então
j  j+1; Fim;
Se (t  V[j]) Então
Parar loop;
Senão
V[k]  V[j]; k  j;

V[k]  t; Complexidade: (n)!!

Fim;

Filas de Prioridade Filas de Prioridade

Heaps Heaps
Criação de um Heap a partir de um vetor já pre- Criação de um Heap a partir de um vetor já pre-
enchido, usando DESCEHEAP. enchido, usando DESCEHEAP.
1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10
Exemplo: Exemplo:
1 28 17 18 2 17 1 17 50 3 1 28 17 18 3 17 1 17 50 2
1 1

28 17 28 17

18 2 17 1 18 3 17 1

17 50 3 17 50 2

4
 Filas de Prioridade Filas de Prioridade

Heaps Heaps
Criação de um Heap a partir de um vetor já pre- Criação de um Heap a partir de um vetor já pre-
enchido, usando DESCEHEAP. enchido, usando DESCEHEAP.
1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10
Exemplo: Exemplo:
1 28 17 50 3 17 1 17 18 2 1 28 17 50 3 17 1 17 18 2
1 1

28 17 28 17

50 3 17 1 50 3 17 1

17 18 2 17 18 2

Filas de Prioridade Filas de Prioridade

Heaps Heaps
Criação de um Heap a partir de um vetor já pre- Criação de um Heap a partir de um vetor já pre-
enchido, usando DESCEHEAP. enchido, usando DESCEHEAP.
1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10
Exemplo: Exemplo:
1 50 17 28 3 17 1 17 18 2 50 28 17 18 3 17 1 17 1 2
1 50
50 17 28 17
28 3 17 1 18 3 17 1
17 18 2 17 1 2

Filas de Prioridade Filas de Prioridade

Heaps Heaps
Criação de um Heap a partir de um vetor já pre- Complexidade da criação de um Heap a partir de
enchido, usando DESCEHEAP. um vetor já preenchido, usando DESCEHEAP.

NC = 2 1  i  (h -1) 2i-1(h - i)
= 2( 1  i  (h -1) h.2i-1 - 1  i  (h -1) i.2i-1)
Exercício: Criar um Heap a partir do vetor = 2(h 1 ≤ i ≤ (h-1) 2i-1 - (1/2) i1 ≤ i ≤ (h-1) i.2i)
preenchido com o MIXTRING (10 letras) = 2(h(2h-1 - 1) - (2h-1 - (h - 2) + 1))
usando DesceHeap. = 2(h.2h-1 - h - h.2h-1 - h + 2h - 1)
= 2(2h - h - 1) = 2h+1 - 2.h - 2

Quando (n + 1) é potência de 2, temos 2h = (n + 1)

NC = 2((n+1) - log2(n + 1) - 1) =
= 2(n+1 - log2(n + 1) - 1) =
= 2(n - log2(n + 1)) =
= (n)

5
 Filas de Prioridade Filas de Prioridade

Heaps Heapsort
Operações em um Heap:
Idéia: criar um Heap e, sucessivamente, trocar
Inserção:
o primeiro elemento com o último, diminuir o Heap
Inserção no final do vetor + SOBEHEAP.
e acertá-lo.
Retirada do elemento de maior prioridade: Heapsort:
Substituição pelo último elemento + DESCEHEAP. #Dados: Vetor V com n elementos
CriaHeap;

Modificação de prioridade: Para i decrescendo de n a 2:

Troca (1, i);
SOBEHEAP ou DESCEHEAP. DesceHeap(1, i-1);

Deleção: Fim;
Substituição pelo último elemento + Modificação
de prioridade.

Filas de Prioridade Filas de Prioridade

Heapsort Heapsort
Passo 1: Criação do Heap.
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
Exemplo: 1 28 17 18 2 17 1 17 50 3 Exemplo:
50 28 17 18 3 17 1 17 1 2
1 50
28 17 28 17
18 2 17 1 18 3 17 1
17 50 3 17 1 2

Filas de Prioridade Filas de Prioridade

Heapsort Heapsort
Passo 2: i = 10  Troca primeiro com último. Passo 2: i = 10  DesceHeap (1,9).

1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10
Exemplo: 2 28 17 18 3 17 1 17 1 50 Exemplo: 28 18 17 17 3 17 1 2 1 50

2 28

28 17 18 17

18 3 17 1 17 3 17 1

17 1 50 2 1

6
 Filas de Prioridade Filas de Prioridade

Heapsort Heapsort
Passo 2: i = 9  Troca primeiro com último. Passo 2: i = 9  DesceHeap (1,8).

1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10
Exemplo: 1 18 17 17 3 17 1 2 28 50 Exemplo: 18 17 17 2 3 17 1 1 28 50

1 18

18 17 17 17

17 3 17 1 2 3 17 1

2 28 1

Filas de Prioridade Filas de Prioridade

Heapsort Heapsort
Passo 2: i = 8  Troca primeiro com último. Passo 2: i = 8  DesceHeap (1,7).

1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10
Exemplo: 1 17 17 2 3 17 1 18 28 50 Exemplo: 17 3 17 2 1 17 1 18 28 50

1 17

17 17 3 17

2 3 17 1 2 1 17 1

18

Filas de Prioridade Filas de Prioridade

Heapsort Heapsort
Passo 2: i = 7  Troca primeiro com último. Passo 2: i = 7  DesceHeap (1,6).

1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10
Exemplo: 1 3 17 2 1 17 17 18 28 50 Exemplo: 17 3 17 2 1 1 17 18 28 50

1 17

3 17 3 17

2 1 17 17 2 1 1

7
 Filas de Prioridade Filas de Prioridade

Heapsort Heapsort
Passo 2: i = 6  Troca primeiro com último. Passo 2: i = 6  DesceHeap (1,5).

1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10
Exemplo: 1 3 17 2 1 17 17 18 28 50 Exemplo: 17 3 1 2 1 17 17 18 28 50

1 17

3 17 3 1

2 1 17 2 1

Filas de Prioridade Filas de Prioridade

Heapsort Heapsort
Passo 2: i = 5  Troca primeiro com último. Passo 2: i = 5  DesceHeap (1,4).

1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10
Exemplo: 1 3 1 2 17 17 17 18 28 50 Exemplo: 3 2 1 1 17 17 17 18 28 50

1 3

3 1 2 1

2 17 1

Filas de Prioridade Filas de Prioridade

Heapsort Heapsort
Passo 2: i = 4  Troca primeiro com último. Passo 2: i = 4  DesceHeap (1,3).

1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10
Exemplo: 1 2 1 3 17 17 17 18 28 50 Exemplo: 2 1 1 3 17 17 17 18 28 50

1 2

2 1 1 1

8
 Filas de Prioridade Filas de Prioridade

Heapsort Heapsort
Passo 2: i = 3  Troca primeiro com último. Passo 2: i = 3  DesceHeap (1,2).

1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10
Exemplo: 1 1 2 3 17 17 17 18 28 50 Exemplo: 1 1 2 3 17 17 17 18 28 50

1 1

1 2 1

Filas de Prioridade Filas de Prioridade

Heapsort Heapsort
Passo 2: i = 2  Troca primeiro com último. Passo 2: i = 2  DesceHeap (1,1).

1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10
Exemplo: 1 1 2 3 17 17 17 18 28 50 Exemplo: 1 1 2 3 17 17 17 18 28 50

1 1

Filas de Prioridade Filas de Prioridade

Heapsort Heapsort
Análise do HEAPSORT:
HEAPSORT
Complexidade:
Pior caso: O(n log n) vetor inv. ordenado
Melhor caso: O(n) chaves iguais
Exercício: Ordenar o MIXTRING (10 letras) Estabilidade (manutenção da ordem relativa de
usando Heapsort. chaves iguais):
Algoritmo não estável
Memória adicional:
Nenhuma
Usos especiais:
Algoritmo de uso geral

9
Filas de Prioridade

FIM

10