PriorityQueue en Java

PriorityQueue se usa cuando se supone que los objetos se procesarán en función de la prioridad. Se sabe que una Cola sigue el algoritmo First-In-First-Out, pero a veces se necesita procesar los elementos de la cola de acuerdo con la prioridad, ahí es cuando entra en juego PriorityQueue.

PriorityQueue se basa en el montón de prioridad. Los elementos de la cola de prioridad se ordenan según el ordenamiento natural o mediante un comparador proporcionado en el momento de la construcción de la cola, según el constructor que se utilice.  

En la cola de prioridad a continuación, un elemento con un valor ASCII máximo tendrá la prioridad más alta.

Declaración:

public class PriorityQueue<E> extends AbstractQueue<E> implements Serializable

where E is the type of elements held in this queue

La clase implementa las interfaces Serializable , Iterable<E> , Collection<E> , Queue<E> .

Algunos puntos importantes en Priority Queue son los siguientes: 

• PriorityQueue no permite valores nulos.
• No podemos crear una PriorityQueue de objetos que no son comparables
• PriorityQueue son colas independientes.
• La cabeza de esta cola es el elemento menor con respecto al orden especificado. Si varios elementos están empatados por el valor mínimo, la cabeza es uno de esos elementos: los empates se rompen arbitrariamente.
• Dado que PriorityQueue no es seguro para subprocesos, Java proporciona la clase PriorityBlockingQueue que implementa la interfaz BlockingQueue para usar en un entorno de subprocesos múltiples de Java.
• Las operaciones de recuperación de la cola sondean, eliminan, observan y el elemento accede al elemento que se encuentra al principio de la cola.
• Proporciona tiempo O(log(n)) para los métodos de adición y sondeo.
• Hereda métodos de AbstractQueue , AbstractCollection , Collection y Object class.

Constructores:

1. PriorityQueue(): crea una PriorityQueue con la capacidad inicial predeterminada (11) que ordena sus elementos según su orden natural.

PriorityQueue<E> pq = new PriorityQueue<E>();

2. PriorityQueue(Collection<E> c): crea una PriorityQueue que contiene los elementos de la colección especificada.

PriorityQueue<E> pq = new PriorityQueue<E>(Colección<E> c);

3. PriorityQueue(int initialCapacity) : crea una PriorityQueue con la capacidad inicial especificada que ordena sus elementos según su ordenación natural.

PriorityQueue<E> pq = new PriorityQueue<E>(int initialCapacity);

4. PriorityQueue(int initialCapacity, Comparator<E> comparador): Crea un PriorityQueue con la capacidad inicial especificada que ordena sus elementos de acuerdo con el comparador especificado.

PriorityQueue<E> pq = new PriorityQueue(int initialCapacity, Comparator<E> comparador);

5. PriorityQueue(PriorityQueue<E> c) : Crea una PriorityQueue que contiene los elementos en la cola de prioridad especificada.

PriorityQueue<E> pq = new PriorityQueue(PriorityQueue<E> c);

6. PriorityQueue(SortedSet<E> c) : crea una PriorityQueue que contiene los elementos del conjunto ordenado especificado.

PriorityQueue<E> pq = new PriorityQueue<E>(SortedSet<E> c);

Ejemplo:

El siguiente ejemplo explica las siguientes operaciones básicas de la cola de prioridad.

• boolean add (elemento E): este método inserta el elemento especificado en esta cola de prioridad.
• ojeada pública(): este método recupera, pero no elimina, el encabezado de esta cola o devuelve un valor nulo si esta cola está vacía.
• encuesta pública(): este método recupera y elimina el encabezado de esta cola, o devuelve un valor nulo si esta cola está vacía.

// Java program to demonstrate the
// working of PriorityQueue
import java.util.*;
  
class PriorityQueueDemo {
    
      // Main Method
    public static void main(String args[])
    {
        // Creating empty priority queue
        PriorityQueue<Integer> pQueue = new PriorityQueue<Integer>();
  
        // Adding items to the pQueue using add()
        pQueue.add(10);
        pQueue.add(20);
        pQueue.add(15);
  
        // Printing the top element of PriorityQueue
        System.out.println(pQueue.peek());
  
        // Printing the top element and removing it
        // from the PriorityQueue container
        System.out.println(pQueue.poll());
  
        // Printing the top element again
        System.out.println(pQueue.peek());
    }
}

10
10
15

Operaciones en PriorityQueue

Veamos cómo realizar algunas operaciones de uso frecuente en la clase Priority Queue.

1. Agregar elementos: para agregar un elemento en una cola de prioridad, podemos usar el método add() . El pedido de inserción no se conserva en PriorityQueue. Los elementos se almacenan según el orden de prioridad que es ascendente por defecto. 

/*package whatever //do not write package name here */
  
import java.util.*;
import java.io.*;
    
public class PriorityQueueDemo {
    
    public static void main(String args[])
    {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for(int i=0;i<3;i++){
            pq.add(i);
            pq.add(1);
        }
        System.out.println(pq);
    }
}

[0, 1, 1, 1, 2, 1]

No obtendremos elementos ordenados imprimiendo PriorityQueue.

/*package whatever //do not write package name here */
  
import java.util.*;
import java.io.*;
    
public class PriorityQueueDemo {
    
    public static void main(String args[])
    {
        PriorityQueue<String> pq = new PriorityQueue<>();
    
        pq.add("Geeks");
        pq.add("For");
        pq.add("Geeks");
    
        System.out.println(pq);
    }
}

[For, Geeks, Geeks]

2. Eliminación de elementos: para eliminar un elemento de una cola de prioridad, podemos usar el método remove() . Si hay varios de estos objetos, se elimina la primera aparición del objeto. Aparte de eso, el método poll() también se usa para quitar la cabeza y devolverla.

// Java program to remove elements
// from a PriorityQueue
  
import java.util.*;
import java.io.*;
  
public class PriorityQueueDemo {
  
    public static void main(String args[])
    {
        PriorityQueue<String> pq = new PriorityQueue<>();
  
        pq.add("Geeks");
        pq.add("For");
        pq.add("Geeks");
  
        System.out.println("Initial PriorityQueue " + pq);
  
          // using the method
        pq.remove("Geeks");
  
        System.out.println("After Remove - " + pq);
  
        System.out.println("Poll Method - " + pq.poll());
  
        System.out.println("Final PriorityQueue - " + pq);
    }
}

Initial PriorityQueue [For, Geeks, Geeks]
After Remove - [For, Geeks]
Poll Method - For
Final PriorityQueue - [Geeks]

3. Acceder a los elementos: Dado que Queue sigue el principio First In First Out, solo podemos acceder a la cabeza de la cola. Para acceder a los elementos de una cola de prioridad, podemos usar el método peek().
 

// Java program to access elements
// from a PriorityQueue
import java.util.*;
  
class PriorityQueueDemo {
    
      // Main Method
    public static void main(String[] args)
    {
  
        // Creating a priority queue
        PriorityQueue<String> pq = new PriorityQueue<>();
        pq.add("Geeks");
        pq.add("For");
        pq.add("Geeks");
        System.out.println("PriorityQueue: " + pq);
  
        // Using the peek() method
        String element = pq.peek();
        System.out.println("Accessed Element: " + element);
    }
}

PriorityQueue: [For, Geeks, Geeks]
Accessed Element: For

4. Iteración de PriorityQueue: hay varias formas de iterar a través de PriorityQueue. La forma más famosa es convertir la cola en una array y atravesarla usando el bucle for. Sin embargo, la cola también tiene un iterador incorporado que se puede usar para iterar a través de la cola.

// Java program to iterate elements
// to a PriorityQueue
  
import java.util.*;
  
public class PriorityQueueDemo {
  
      // Main Method
    public static void main(String args[])
    {
        PriorityQueue<String> pq = new PriorityQueue<>();
  
        pq.add("Geeks");
        pq.add("For");
        pq.add("Geeks");
  
        Iterator iterator = pq.iterator();
  
        while (iterator.hasNext()) {
            System.out.print(iterator.next() + " ");
        }
    }
}

For Geeks Geeks 

Métodos en la clase PriorityQueue

Métodos declarados en la clase java.util.AbstractQueue

Métodos declarados en la clase java.util.AbstractCollection

Métodos declarados en la interfaz java.util.Collection

Métodos declarados en la interfaz java.util.Queue

Aplicaciones : 

• Implementación de los algoritmos de Dijkstra y Prim .
• Maximizar la suma de arrays después de K negaciones

Artículos relacionados : 

• Clase Java.util.PriorityQueue en Java
• Implementar PriorityQueue a través de Comparator en Java

Este artículo es una contribución de Mehak Kumar. Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.