Implemetação em Java de uma `MaxPriorityQueue`

public class MaxPriorityQueue {
    private int[] heap;    // array que armazena o heap (1-based)
    private int size;      // quantidade de elementos atualmente no heap
    private int capacity;  // capacidade máxima

    // Construtor: define capacidade máxima
    public MaxPriorityQueue(int capacity) {
        this.capacity = capacity;
        this.heap = new int[capacity + 1]; // índice 0 fica “vazio” para facilitar os cálculos
        this.size = 0;
    }

    // Insere um novo valor na fila de prioridade
    public void insert(int value) {
        if (size >= capacity) {
            throw new RuntimeException("Capacidade excedida");
        }
        size++;
        heap[size] = value;
        siftUp(size);
    }

    // Remove e retorna o elemento de maior prioridade (raiz do heap)
    public int extractMax() {
        if (isEmpty()) {
            throw new RuntimeException("Fila vazia");
        }
        int max = heap[1];
        heap[1] = heap[size];
        size--;
        siftDown(1);
        return max;
    }

    // Apenas consulta o máximo sem remover
    public int peek() {
        if (isEmpty()) {
            throw new RuntimeException("Fila vazia");
        }
        return heap[1];
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public int size() {
        return size;
    }

    // Ajusta para cima: enquanto pai for menor, troca com o filho
    private void siftUp(int idx) {
        while (idx > 1 && heap[idx] > heap[idx / 2]) {
            swap(idx, idx / 2);
            idx = idx / 2;
        }
    }

    // Ajusta para baixo: compara com os filhos e garante propriedade de max-heap
    private void siftDown(int idx) {
        int largest = idx;
        int left  = 2 * idx;
        int right = 2 * idx + 1;

        if (left  <= size && heap[left]  > heap[largest]) largest = left;
        if (right <= size && heap[right] > heap[largest]) largest = right;

        if (largest != idx) {
            swap(idx, largest);
            siftDown(largest);
        }
    }

    // Troca dois elementos no array
    private void swap(int i, int j) {
        int tmp = heap[i];
        heap[i] = heap[j];
        heap[j] = tmp;
    }

    // Exemplo de uso
    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
    }
}

Fundamentos Teóricos da Fila de Prioridade

Conceito e Definição

Uma fila de prioridade é uma estrutura de dados que mantém uma coleção de elementos, cada um com uma prioridade associada, permitindo a extração do elemento com maior (ou menor) prioridade independentemente da ordem de inserção 1 5 6. Diferentemente das filas convencionais que seguem o princípio FIFO (First-In-First-Out), as filas de prioridade atendem primeiro os elementos com maior prioridade, tornando-as ideais para situações onde certos elementos precisam ser processados antes de outros 2 7 8.

Propriedades Essenciais

As filas de prioridade possuem duas operações fundamentais: inserção de novos elementos e remoção do elemento de maior prioridade 1 3 6. Estas operações devem ser eficientes para garantir o bom desempenho da estrutura em aplicações reais 4 5. A propriedade principal que deve ser mantida é que o elemento de maior prioridade esteja sempre acessível em tempo constante, independentemente do número de elementos na fila 2 6 7.

Tipos de Filas de Prioridade

Existem dois tipos principais de filas de prioridade: o heap máximo, onde o elemento de maior valor tem prioridade máxima, e o heap mínimo, onde o elemento de menor valor tem prioridade máxima 2 5 11. A escolha entre eles depende da aplicação específica e da definição de prioridade utilizada no contexto do problema 5 7 8.

Implementações de Filas de Prioridade

Estruturas de Dados para Implementação

Diversas estruturas de dados podem ser utilizadas para implementar filas de prioridade, cada uma com vantagens e desvantagens específicas 1 2 5. As implementações mais comuns incluem arrays ordenados, arrays não ordenados, listas ligadas, heaps binários e árvores de busca balanceadas 4 5 14.

Comparação de Complexidade Temporal entre Implementações de Fila de Prioridade

Heap Binário como Implementação Eficiente

O heap binário é considerado a implementação mais eficiente e comum para filas de prioridade, pois oferece um bom equilíbrio entre complexidade de tempo para inserção e remoção 5 10 11. Um heap binário é uma árvore binária completa que satisfaz a propriedade de heap: para qualquer nó, o valor do nó pai é maior (ou menor) que os valores de seus filhos 1 10 11.

Implemetação em Java de uma MaxPriorityQueue