Filas de Prioridade e Huffman

1. O Conceito de Fila de Prioridade

Em uma fila comum (FIFO), o primeiro a chegar é o primeiro a ser atendido. Em uma Fila de Prioridade, cada elemento tem uma “urgência” associada. O elemento de maior prioridade é sempre atendido primeiro, não importa quando chegou. Exemplos: - Triagem de Hospital (Emergência > Dor de garganta). - Agendador de CPU (Processo de Sistema > Processo de Usuário). - Algoritmo de Dijkstra (Menor distância atual > Maior distância).

A estrutura de dados mais eficiente para implementar isso é o Heap Binário.

2. Heap Binário

Um Heap é uma Árvore Binária Quase Completa (preenchida da esquerda p/ direita) que satisfaz a Propriedade do Heap: - Max-Heap: Pai \(\ge\) Filhos (Raiz é o Maior). - Min-Heap: Pai \(\le\) Filhos (Raiz é o Menor).

Representação em Vetor (Array)

Como a árvore é completa, não precisamos de ponteiros left e right. Podemos armazenar tudo em um vetor linear! Para um nó no índice \(i\) (indexado em 1): - Pai: \(\lfloor i/2 \rfloor\) - Filho Esquerdo: \(2 \times i\) - Filho Direito: \(2 \times i + 1\)

Operações Principais

  1. Insert (\(O(\log N)\)): Adiciona o elemento no final do vetor (primeira folha livre) e faz o Sift-Up (troca com o pai enquanto for maior que ele).
  2. Extract-Max (\(O(\log N)\)):
    • Retira a Raiz (índice 1).
    • Coloca o último elemento do vetor na Raiz.
    • Faz o Sift-Down (troca com o maior filho até restaurar a propriedade).

3. Prática em Java (PriorityQueue)

O Java possui a classe PriorityQueue implementando um Min-Heap.

import java.util.PriorityQueue;
import java.util.Collections;

public class ExemploHeap {
    public static void main(String[] args) {
        // Padrão: Min-Heap (Menor sai primeiro)
        PriorityQueue<Integer> minh = new PriorityQueue<>();
        
        minh.add(10);
        minh.add(5);
        minh.add(20);
        
        System.out.println(minh.poll()); // Remove e imprime 5
        System.out.println(minh.poll()); // Remove e imprime 10
        
        // Para Max-Heap: Usar Collections.reverseOrder()
        PriorityQueue<Integer> maxh = new PriorityQueue<>(Collections.reverseOrder());
        
        maxh.add(10);
        maxh.add(5);
        maxh.add(20);
        
        System.out.println(maxh.poll()); // Remove e imprime 20
    }
}

HeapSort

Uma aplicação direta é ordenar um vetor em \(O(N \log N)\) e espaço \(O(1)\) extra (se feito in-place). 1. Construa um Max-Heap a partir vetor desordenado. 2. Troque a Raiz (maior) com o último. 3. Reduza o tamanho do heap e chame Sift-Down na nova raiz. 4. Repita.

4. Compressão de Huffman

O algoritmo de Huffman usa uma Fila de Prioridade para compressão de dados Lossless (sem perda). A ideia é usar códigos binários menores para caracteres mais frequentes.

Algoritmo Guloso

  1. Conte a frequência de cada caractere na string.
  2. Crie um nó folha para cada caractere e insira em uma Min-PriorityQueue.
  3. Enquanto houver mais de 1 nó na fila:
    1. Remova os dois nós de menor frequência (\(A\) e \(B\)).
    2. Crie um novo nó interno \(P\) com frequência = \(freq(A) + freq(B)\).
    3. Faça \(A\) e \(B\) serem filhos de \(P\).
    4. Insira \(P\) na fila.
  4. O nó restante é a raiz da Árvore de Huffman.

Exemplo

Texto: “banana” (\(b:1, n:2, a:3\)). Fila: [(b,1), (n,2), (a,3)]

  1. Tira (b,1) e (n,2). Soma = 3. Cria nó (bn, 3). Fila: [(bn, 3), (a, 3)]. (Ordem depende de desempate).
  2. Tira (bn, 3) e (a, 3). Soma = 6. Cria Raiz (Total, 6).

Códigos: Caminhar para esquerda = 0, direita = 1. Se ‘a’ ficar na direita da raiz -> Código 1 (1 bit). Se ‘b’ ficar em esquerda->esquerda -> Código 00 (2 bits).

Implementação Simplificada do Nó:

class HuffmanNode implements Comparable<HuffmanNode> {
    char c;
    int frequency;
    HuffmanNode left, right;
    
    public int compareTo(HuffmanNode other) {
        return this.frequency - other.frequency;
    }
}

5. Aplicações de Heaps em Grafos

Heaps são o “motor” de algoritmos vitais de Grafos: 1. Algoritmo de Dijkstra: O heap decide qual vértice explorar em seguida (o de menor distância acumulada). Isso reduz a complexidade de \(O(V^2)\) para \(O(E \log V)\). 2. Algoritmo de Prim: Para Árvore Geradora Mínima, similar ao Dijkstra.

Exercícios Sugeridos: - Beecrowd 1252: Sort! (Custom Comparator). - LeetCode 215: Kth Largest Element in an Array (Use um Min-Heap de tamanho K). - LeetCode 23: Merge k Sorted Lists.

Back to top