Estrutura

Anotacoes

Estrutura de Dados II 5ª parte Profª. Camilla Lobo Paulino Camilla.paulino@uva.br Estrutura de Dados II2 Heap ➢ É um tipo particular de Árvore Binária que implementa uma fila de prioridades. ➢ Uma fila de prioridades é uma sequência de elementos organizada segundo um critério que define a prioridade de um elemento sobre outro. ➢ Por se tratar de uma fila, a prioridade é que vai definir se um elemento vem antes ou depois de outro. ➢ É possível implementar uma fila de prioridades usando uma lista. ➢ Entretanto, por razões de eficiência, podemos usar heaps. Estrutura de Dados II3 Heap ➢ Um heap é representado por uma árvore binária completa:  Á árvore está cheia, ou;  Elementos faltantes aparecem apenas no nível mais baixo na subárvore da direita. Estrutura de Dados II4 Heap ➢ Um heap é representado por uma árvore binária completa:  Á árvore está cheia.  Elementos faltantes aparecem apenas no nível mais baixo na subárvore da direita. Ignorando o último nível, temos uma árvore cheia. Estrutura de Dados II5 Heap ➢ Um heap é representado por uma árvore binária completa:  Á árvore está cheia.  Elementos faltantes aparecem apenas no nível mais baixo na subárvore da direita. Se o últi...