Filas de Prioridade (MinHeap)

// -----------------------------------------------------------
// Estruturas de Dados 2019/2020 (CC1007) - DCC/FCUP
// http://www.dcc.fc.up.pt/~pribeiro/aulas/edados1920/
// -----------------------------------------------------------
// Fila de Prioridade (com uma minHeap)
// Em caso de empate no minimo, devolve um qualquer (dos minimos)
// Ultima alteração: 05/06/2020
// -----------------------------------------------------------

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 2019/2020 (CC1007) - DCC/FCUP
// http://www.dcc.fc.up.pt/~pribeiro/aulas/edados1920/
// -----------------------------------------------------------
// Teste da MinHeap
// Ultima alteração: 18/05/2018
// -----------------------------------------------------------

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();
   }
}