Java PriorityQueue

Cola de prioridad de Java

En este tutorial, aprenderemos sobre la clase PriorityQueue del marco de colecciones de Java con la ayuda de ejemplos.

El PriorityQueue class proporciona la funcionalidad de la estructura de datos del montón.

Implementa la interfaz Queue.

A diferencia de las colas normales, los elementos de la cola de prioridad se recuperan en orden.

Supongamos que queremos recuperar elementos en orden ascendente. En este caso, la cabeza de la cola de prioridad será el elemento más pequeño. Una vez que se recupera este elemento, el siguiente elemento más pequeño será el encabezado de la cola.

Es importante tener en cuenta que los elementos de una cola de prioridad no se pueden ordenar. Sin embargo, los elementos siempre se recuperan en orden.

Creando PriorityQueue

Para crear una cola de prioridad, debemos importar el java.util.PriorityQueue paquete. Una vez que importamos el paquete, así es como podemos crear una cola de prioridad en Java.

PriorityQueue<Integer> numbers = new PriorityQueue<>();

Aquí, hemos creado una cola de prioridad sin ningún argumento. En este caso, la cabeza de la cola de prioridad es el elemento más pequeño de la cola. Y los elementos se eliminan en orden ascendente de la cola.

Sin embargo, podemos personalizar el orden de los elementos con la ayuda de Comparator interfaz. Aprenderemos sobre eso más adelante en este tutorial.

Métodos de PriorityQueue

El PriorityQueue class proporciona la implementación de todos los métodos presentes en el Queue interfaz.

Insertar elementos en PriorityQueue

add() - Inserta el elemento especificado en la cola. Si la cola está llena, lanza una excepción.
offer() - Inserta el elemento especificado en la cola. Si la cola está llena, devuelve false .

Por ejemplo,

import java.util.PriorityQueue;

class Main {
    public static void main(String[] args) {

        // Creating a priority queue
        PriorityQueue<Integer> numbers = new PriorityQueue<>();

        // Using the add() method
        numbers.add(4);
        numbers.add(2);
        System.out.println("PriorityQueue: " + numbers);

        // Using the offer() method
        numbers.offer(1);
        System.out.println("Updated PriorityQueue: " + numbers);
    }
}

Salida

PriorityQueue: [2, 4]
Updated PriorityQueue: [1, 4, 2]

Aquí, hemos creado una cola de prioridad llamada numbers . Hemos insertado 4 y 2 en la cola.

Aunque 4 se inserta antes que 2, la cabeza de la cola es 2. Esto se debe a que la cabeza de la cola de prioridad es el elemento más pequeño de la cola.

Entonces hemos insertado 1 en la cola. La cola ahora se reorganiza para almacenar el elemento 1 más pequeño al principio de la cola.

Acceso a los elementos de PriorityQueue

Para acceder a elementos de una cola de prioridad, podemos usar el peek() método. Este método devuelve la cabeza de la cola. Por ejemplo,

import java.util.PriorityQueue;

class Main {
    public static void main(String[] args) {

        // Creating a priority queue
        PriorityQueue<Integer> numbers = new PriorityQueue<>();
        numbers.add(4);
        numbers.add(2);
        numbers.add(1);
        System.out.println("PriorityQueue: " + numbers);

        // Using the peek() method
        int number = numbers.peek();
        System.out.println("Accessed Element: " + number);
    }
}

Salida

PriorityQueue: [1, 4, 2]
Accessed Element: 1

Eliminar elementos PriorityQueue

remove() - elimina el elemento especificado de la cola
poll() - devuelve y elimina la cabeza de la cola

Por ejemplo,

import java.util.PriorityQueue;

class Main {
    public static void main(String[] args) {

        // Creating a priority queue
        PriorityQueue<Integer> numbers = new PriorityQueue<>();
        numbers.add(4);
        numbers.add(2);
        numbers.add(1);
        System.out.println("PriorityQueue: " + numbers);

        // Using the remove() method
        boolean result = numbers.remove(2);
        System.out.println("Is the element 2 removed? " + result);

        // Using the poll() method
        int number = numbers.poll();
        System.out.println("Removed Element Using poll(): " + number);
    }
}

Salida

PriorityQueue: [1, 4, 2]
Is the element 2 removed? true
Removed Element Using poll(): 1

Iterando sobre una PriorityQueue

Para iterar sobre los elementos de una cola de prioridad, podemos usar el iterator() método. Para usar este método, debemos importar el java.util.Iterator paquete. Por ejemplo,

import java.util.PriorityQueue;
import java.util.Iterator;

class Main {
    public static void main(String[] args) {

        // Creating a priority queue
        PriorityQueue<Integer> numbers = new PriorityQueue<>();
        numbers.add(4);
        numbers.add(2);
        numbers.add(1);
        System.out.print("PriorityQueue using iterator(): ");

        //Using the iterator() method
        Iterator<Integer> iterate = numbers.iterator();
        while(iterate.hasNext()) {
            System.out.print(iterate.next());
            System.out.print(", ");
        }
    }
}

Salida

PriorityQueue using iterator(): 1, 4, 2,

Otros métodos PriorityQueue

Métodos	Descripciones
`contains(element)`	Busca en la cola de prioridad el elemento especificado. Si se encuentra el elemento, devuelve `true` , si no, devuelve `false` .
`size()`	Devuelve la longitud de la cola de prioridad.
`toArray()`	Convierte una cola de prioridad en una matriz y la devuelve.

Comparador de cola de prioridad

En todos los ejemplos anteriores, los elementos de la cola de prioridad se recuperan en el orden natural (orden ascendente). Sin embargo, podemos personalizar este pedido.

Para esto, necesitamos crear nuestra propia clase de comparación que implemente el Comparator interfaz. Por ejemplo,

import java.util.PriorityQueue;
import java.util.Comparator;
class Main {
    public static void main(String[] args) {

        // Creating a priority queue
        PriorityQueue<Integer> numbers = new PriorityQueue<>(new CustomComparator());
        numbers.add(4);
        numbers.add(2);
        numbers.add(1);
        numbers.add(3);
        System.out.print("PriorityQueue: " + numbers);
    }
}

class CustomComparator implements Comparator<Integer> {

    @Override
    public int compare(Integer number1, Integer number2) {
        int value =  number1.compareTo(number2);
        // elements are sorted in reverse order
        if (value > 0) {
            return -1;
        }
        else if (value < 0) {
            return 1;
        }
        else {
            return 0;
        }
    }
}

Salida

PriorityQueue: [4, 3, 1, 2]

En el ejemplo anterior, hemos creado una cola de prioridad que pasa CustomComparator class como argumento.

El Comparador Personalizado clase implementa el Comparator interfaz.

Luego anulamos el compare() método. El método ahora hace que la cabeza del elemento sea el número más grande.

Para obtener más información sobre el comparador, visite Java Comparator.

Interfaz de cola de Java Interfaz Java Deque

Java