Cola de prioridad de par en Java con ejemplos

Requisito previo: PriorityQueue , Par

La clase javafx.util.Pair<K,V> en Java es la combinación de dos objetos diferentes llamados Key y Value . Básicamente proporciona una forma de almacenar un par de dos elementos de datos heterogéneos.

Par <K, V> par = nuevo Par<>(tecla K, valor V)

PriorityQueue<E> es como una cola normalen la que los elementos se ordenan según el orden natural y el comparador o expresión lambda que se pasa en el constructor.

Constructores de cola de prioridad más utilizados

• PriorityQueue<E> pq = new PriorityQueue<E>();
• PriorityQueue<E> pq = new PriorityQueue<E>(Colección<E> c);
• PriorityQueue<E> pq = new PriorityQueue<E>(int initialCapacity);
• PriorityQueue<E> pq = new PriorityQueue(int initialCapacity, Comparator<E> comparador);

PriorityQueue of Pair<K, V> Sintaxis

• PriorityQueue<Pair<K, V>> = new PriorityQueue<>(initialCapacity, Comparator.comparing(Pair::getKey))
• PriorityQueue<Pair<K, V>> = new PriorityQueue<>(Comparator.comparing(Pair::getKey))

Nota: 

• Dado que la clase Pair<K, V> era parte de JavaFX y JavaFX se eliminó de JDK desde JDK 11. Por lo tanto, los pares se pueden usar hasta JDK 10. 
• Es posible que el siguiente código fuente no se ejecute en la mayoría de los IDE en línea, es mejor probarlo en un software sin conexión.

PriorityQueue Implementando Min Heap basado en claves de par 

1. Uso de la expresión Lambda:

import java.util.*;
import java.io.*;
import javafx.util.Pair;
  
class GFG {
    public static void main(String[] args) {
        
        // Priority Queue implementing min heap of Pairs
        // Creating instance of PriorityQueue by passing 
        // Lambda expression as a constructor parameter.
        PriorityQueue<Pair<Integer, String>> pq = 
                              new PriorityQueue<>((a, b) -> a.getKey() - b.getKey());
          
        // Adding objects of Pair<K, V> class by passing 
        // keys and values as parameter in Pair constructor
        pq.add(new Pair<>(8, "fox"));
        pq.add(new Pair<>(4, "quick"));
        pq.add(new Pair<>(2, "the"));
        pq.add(new Pair<>(6, "brown"));
         
        // Printing min heap based on the priority
        while(!pq.isEmpty()){
              System.out.print(pq.remove() +" ");
        }
    }
}

Producción:

2=el 4=rápido 6=marrón 8=zorro

2. Uso de Comparator: Comparator.comparing()

import java.io.*;
import java.util.*;
import javafx.util.Pair;
  
class GFG {
    public static void main(String[] args) {
        
        // Priority Queue implementing min heap of Pairs
        // Creating instance of PriorityQueue by passing 
        // Comparator as a constructor parameter
        PriorityQueue<Pair<Integer, Integer>> pq = 
                               new PriorityQueue<>(Comparator.comparing(Pair::getKey));
          
        // Adding objects of Pair<K, V> class by passing 
        // keys and values as parameter in Pair constructor
        pq.add(new Pair<>(8,80));
        pq.add(new Pair<>(4,70));
        pq.add(new Pair<>(9,40));
        pq.add(new Pair<>(2,85));
          
          // Printing min heap based on the priority
        while(!pq.isEmpty()){
              System.out.print(pq.remove() +" ");
        }
    }
}

Producción:

2=85 4=70 8=80 9=40 

PriorityQueue implementando Max Heap basado en claves de par 

Java por defecto crea PriorityQueue de min heap cuando no especificamos el tipo. Un pequeño cambio en el código anterior puede hacer que se comporte como un montón Max.

// PriorityQueue implementing Max heap
PriorityQueue<Pair<Integer, Integer> > pq = 
       new PriorityQueue<>((a, b) -> b.getKey() - a.getKey());

Otra forma de crear un montón máximo: 

1. Agregando las claves en PriorityQueue después de multiplicarlas por -1. 
2. Pero no olvide convertirlo al formato original (nuevamente multiplicando por -1) mientras lo elimina de la cola y realiza operaciones en ellos.

PriorityQueue Implementando Max Heap y Min Heap en función de los valores del par 

Para crear PriorityQueue en función de los valores de Pair<K, V> simplemente reemplace el método getKey() con el método getValue() .

// PriorityQueue implementing Min heap based on values of Pair<K, V>
PriorityQueue<Pair<Integer, Integer> > pq = 
          new PriorityQueue<>((a, b) -> a.getValue() - b.getValue());
  
// PriorityQueue implementing Max heap based on values of Pair<K, V>
PriorityQueue<Pair<Integer, Integer> > pq = 
          new PriorityQueue<>((a, b) -> b.getValue() - a.getValue());