Apostila Paulo Eustáquio
1387 palavras
6 páginas
Listas de PrioridadeListas de Prioridade
Notas de aula da disciplina IME 04-10820
ESTRUTURAS DE DADOS I
Paulo Eustáquio Duarte Pinto
(pauloedp arroba ime.uerj.br)
Em algumas situações, é necessário manter um conjunto dinâmico de chaves, tal que a principal operação no conjunto é a retirada do elemento de maior prioridade (chave). A manutenção do conjunto ordenado é uma solução para o problema, mas o uso das listas de prioridade fornece uma solução mais simples. Ex: seleção de jobs.
Listas de prioridade são estruturas de dados para as quais se tem operações eficientes para:
-Seleção do elemento de maior prioridade - O(1)
-Inserção/deleção de elementos -O(log n)
-Mudanças de prioridade -O(log n)
fevereiro/2011
Listas de Prioridade
Listas de Prioridade
Heaps
Heaps
Heaps implementam listas de prioridade. Um Heap é uma árvore binária (virtual!), onde a chave de cada nó é ≥ (≤) que a dos descendentes.
≤
Exemplo:
Um Heap é um vetor que pode ser visto como uma árvore binária (virtual!). A raiz é a célula 1 e os filhos do nó i estão nas células 2i e 2i+1, se existirem.
1 2 3 4 5 6 7
50 28 17 18 3 17 1
Exemplo:
50
50
28
18
1
17
28
17
3
8 9 10
1 17 2
4
1
2
2
18
1
17
17
8
9
2
1
17
3
17
5
3
1
7
6
10
Listas de Prioridade
Listas 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
50 28 17 18 3 17 1
Exemplo:
8 9 10 11
1 17 2 29
1 2 3 4 5 6 7
50 29 17 18 28 17 1
Exemplo:
50
29 28
2
18
1
8
4
17
9
2
10
50
1
3
5
29
17
28
29 17
29 3
11
8 9 10 11
1 17 2 3
6
3
1
7
2
18
1
8
4
17
9
2
10
1
17
28
5
17
3
11
6
3
1
7
Listas de Prioridade
Listas de