Um TAD fila de prioridade mantém uma coleção de elementos mantendo maneira de eficiente de inserir elementos e de retirar o elemento mais prioritário (vamos assumir que o mais prioritário é o menor).
Uma maneira de implementar filas de prioridade com operações eficientes em tempo logarítmico é usar um tipo especial de árvores chamadas de heaps. Numa (min)heap, qualquer nó deve sempre ser menor que os seus filhos (o que significa que o menor de todos está na raíz). Além disso, uma heap é uma árvore completa (todos os níveis cheios, excepto potencialmente o último, com os nós colocados o mais à esquerda possível - o que implica que é equilibrada e tem alura O(log n)) e é tipicamente implementada usando um array (onde o nó na posição i tem como filhos os nós nas posições i*2 e i*2+1) [pode espreitar os slides para relembrar]
// ----------------------------------------------------------- // Estruturas de Dados 2023/2024 (CC1007) - DCC/FCUP // https://www.dcc.fc.up.pt/~miguel-areias/teaching/2324/ed/ // ----------------------------------------------------------- // Fila de Prioridade (com uma minHeap) // Em caso de empate no minimo, devolve um qualquer (dos minimos) // (Pedro Ribeiro @ DCC-FCUP) // ----------------------------------------------------------- import java.util.Comparator; public class MinHeap<T> { private T[] data; // Guardar elementos entre posicoes 1 e size private int size; // Quantidade de elementos private Comparator<T> comparator; // Comparador (opcional) // Construtor (heap com uma dada capacidade) @SuppressWarnings("unchecked") // Por causa da criação de um array de genericos MinHeap(int capacity) { data = (T[]) new Object[capacity+1]; // Java proibe directamente array de genericos, dai o cast size = 0; comparator = null; } // Construtor (heap com uma dada capacidade e comparador customizado) MinHeap(int capacity, Comparator<T> comp) { this(capacity); comparator = comp; } // Numero de elementos guardados na heap public int size() { return size; } // Heap vazia? public boolean isEmpty() { return size==0; } // --------------------------------------------------------------------- // Inserir um elemento na heap public void insert(T value) { if (size + 1 >= data.length) throw new RuntimeException("Heap is full"); size++; data[size] = value; upHeap(size); } // Devolver (sem retirar) elemento minimo public T min() { if (isEmpty()) return null; return data[1]; } // Remover e devolver elemento minimo public T removeMin() { if (isEmpty()) return null; T min = data[1]; data[1] = data[size]; data[size] = null; // Para ajudar no garbage collection size--; downHeap(1); return min; } // --------------------------------------------------------------------- // Fazer um elemento subir na heap ate a sua posição private void upHeap(int i) { while (i>1 && smaller(i, i/2)) { // Enquanto o elemento for menor que o pai e não estiver na raiz swap(i, i/2); // Trocar com o pai i = i/2; } } // Fazer um elemento descer na heap ate a sua posição private void downHeap(int i) { while (2*i <= size) { // Enquanto estiver dento dos limites da heap int j = i*2; if (j<size && smaller(j+1, j)) j++; // Escolher filho mais pequeno (posicao i*2 ou i*2+1) if (smaller(i, j)) break; // Se no ja e menor que filho mais pequeno, terminamos swap(i, j); // Caso contrario, trocar com filho mais pequeno i = j; } } // Saber o elemento na posição i e menor que o elemento na posição j @SuppressWarnings("unchecked") // Para que o java não se queixe do cast que diz que elementos são comparaveis private boolean smaller(int i, int j) { if (comparator == null) // Se não existe comparador usar comparação natural return ((Comparable<? super T>) data[i]).compareTo(data[j]) < 0; else // Se existe comparador... usa-lo return comparator.compare(data[i], data[j]) < 0; } // Trocar elementos entre as posições i e j private void swap(int i, int j) { T tmp = data[i]; data[i] = data[j]; data[j] = tmp; } }
// ----------------------------------------------------------- // Estruturas de Dados 2023/2024 (CC1007) - DCC/FCUP // https://www.dcc.fc.up.pt/~miguel-areias/teaching/2324/ed/ // ----------------------------------------------------------- // Teste da MinHeap // (Pedro Ribeiro @ DCC-FCUP) // ----------------------------------------------------------- import java.util.Comparator; public class TestMinHeap { public static void main(String[] args) { // Criar uma heap h (para inteiros) com capacidade para 100 elementos MinHeap<Integer> h1 = new MinHeap<>(100); // Criar um array com 10 inteiros int[] v1 = {10,4,3,12,9,1,7,11,5,4}; // Inserir na heap h todos os elementos do array v1[] for (int i=0; i<v1.length; i++) h1.insert(v1[i]); // Retirar um a um os elementos e imprimir (empates são resolvidos "aleatoriamente") for (int i=0; i<v1.length; i++) System.out.print(h1.removeMin() + " "); System.out.println(); // ---------------------------------------------- // Criar uma heap h (para strings) com capacidade para 100 elementos MinHeap<String> h2 = new MinHeap<>(100); // Criar um array com 5 strings String[] v2 = {"bbb", "aaaaa", "ee", "cccc", "d"}; // Inserir na heap h todos os elementos do array v2[] for (int i=0; i<v2.length; i++) h2.insert(v2[i]); // Retirar um a um os elementos e imprimir (ordem natural e alfabetica) for (int i=0; i<v2.length; i++) System.out.print(h2.removeMin() + " "); System.out.println(); // ---------------------------------------------- // Criar uma heap h (para strings) com comparador customizado (definido em baixo) MinHeap<String> h = new MinHeap<>(100, new LengthComparator()); // Inserir na heap h todos os elementos do array v2[] criado anteriormento for (int i=0; i<v2.length; i++) h.insert(v2[i]); // Retirar um a um os elementos e imprimir (por ordem crescente de tamanho) for (int i=0; i<v2.length; i++) System.out.print(h.removeMin() + " "); System.out.println(); } } // ---------------------------------------------------------------------------------- // Comparador customizado para strings (comparar tamanho) class LengthComparator implements Comparator<String> { // Assumindo que não são nulas public int compare(String a, String b) { // Conseguem perceber porque podemos subtrair? // Quando e que a subtração da um numero negativo? E positivo? E zero? return a.length() - b.length(); } }
Execute a classe de teste das filas de prioridade: $ java TestMinHeap, acompanhando a execução dos métodos, e espreitando também o código que está em MinHeap.java para ver como é implementada um heap de mínimo.