Algoritmo de Fila de Prioridade

1 / 12

Algoritmo de Fila de Prioridade

Uma estrutura de dados fundamental em Ciência da Computação

Conceitos Fundamentais

Fila de prioridade é uma estrutura de dados que organiza elementos de acordo com suas prioridades, não pela ordem de chegada como filas normais.

Diferença Fundamental:

  • Fila Normal (FIFO): Primeiro a entrar, primeiro a sair
  • Fila de Prioridade: Maior prioridade sai primeiro

Características e Propriedades

Cada elemento possui uma prioridade associada. O elemento de maior (ou menor) prioridade é sempre atendido primeiro.

Ordenação por Prioridade

Elementos são organizados por importância

Acesso Eficiente

Acesso rápido ao elemento prioritário

Flexibilidade

Permite múltiplas implementações

Implementações Possíveis

Array Ordenado

Mantém elementos sempre ordenados

Insert: O(n) | Extract: O(1)

Lista Ligada

Inserção na posição correta

Insert: O(n) | Extract: O(1)

Heap Binário

Implementação mais eficiente

Insert: O(log n) | Extract: O(log n)

Árvore de Busca Binária

Estrutura balanceada

Insert: O(log n) | Extract: O(log n)

Heap Binário

Árvore binária completa que satisfaz a propriedade de heap: cada nó é maior (max-heap) ou menor (min-heap) que seus filhos.

Max-Heap

Pai ≥ Filhos

Raiz = Maior Elemento

Min-Heap

Pai ≤ Filhos

Raiz = Menor Elemento

Vantagem: Implementação eficiente usando array, onde para índice i:

  • Pai: (i-1)/2
  • Filho esquerdo: 2i+1
  • Filho direito: 2i+2

Operações Básicas

Insert

Adiciona elemento mantendo propriedade heap

Extract-Max/Min

Remove e retorna elemento prioritário

Peek/Top

Consulta elemento prioritário sem remover

Decrease-Key

Diminui prioridade de um elemento

Increase-Key

Aumenta prioridade de um elemento

Análise de Complexidade

Operação
Heap Binário
Array Ordenado
Lista Ligada
Insert
O(log n)
O(n)
O(n)
Extract
O(log n)
O(1)
O(1)
Peek
O(1)
O(1)
O(1)

Heap Binário oferece o melhor equilíbrio entre eficiência de inserção e extração.

Aplicações Práticas

Sistemas Operacionais

Escalonamento de processos por prioridade

Algoritmos de Grafos

Menor caminho, árvore geradora mínima

Simulação de Eventos

Ordenação temporal de eventos discretos

Compressão de Dados

Algoritmos de codificação como Huffman

Algoritmos que Usam Filas de Prioridade

Dijkstra

Menor caminho em grafos ponderados

Prim

Árvore geradora mínima

Huffman

Codificação de dados por frequência

A* (A-Star)

Busca informada com heurística

Heapsort

Algoritmo de ordenação eficiente

Implementação em Código

Demonstração prática em Java

public static void main(String[] args) {
        MaxPriorityQueue pq = new MaxPriorityQueue(10);

        // Inserindo valores
        pq.insert(15);
        pq.insert(10);
        pq.insert(30);
        pq.insert(20);
        pq.insert(40);

        System.out.println("Maior elemento (peek): " + pq.peek()); // 40

        // Extraindo em ordem de prioridade
        while (!pq.isEmpty()) {
            System.out.println("Extracted: " + pq.extractMax());
        }
        // Saída esperada: 40, 30, 20, 15, 10
    }

Exercícios Práticos

Exercício 1

Implementar um sistema de prioridades para atendimento médico

Exercício 2

Resolver o problema do menor caminho usando Dijkstra

Exercício 3

Criar um simulador de eventos discretos

Exercício 4

Implementar Heapsort do zero

Dica: Comece com implementações simples e gradualmente otimize para casos mais complexos.

Conclusão

Filas de prioridade são fundamentais para algoritmos eficientes em diversas áreas da computação.

🎯 Eficiência

Heap binário oferece O(log n) para operações principais

🔧 Versatilidade

Aplicável em sistemas operacionais, grafos, simulações

📚 Fundamento

Base para algoritmos clássicos como Dijkstra e Prim

Domine filas de prioridade para ser um programador mais eficiente!