Java Priority Queue: no es una cola clásica

En este artículo, aprendemos una cola de prioridad, clase Java, que implementa la interfaz Queue. ¿Qué sabe un programador de la interfaz de cola regular? En primer lugar, esta interfaz se basa en el principio FIFO o “primero en entrar, primero en salir”. Eso recuerda una cola regular en su significado común. ¿Quieres tomar café de McDrive? Si su coche es el primero en acercarse a la ventana, obtendrá su café antes que el conductor que le sigue.

Declaración de interfaz de cola

public interface Queue<E> extends Collection<E>

¿Qué es una cola de prioridad?

¿Qué es una cola de prioridad? En primer lugar, es una clase que implementa la interfaz Queue en caso de insertar un elemento desde atrás y eliminar un elemento desde la cabeza. Sin embargo, no es una cola habitual en el interior. El orden de los elementos de la cola de prioridad de Java depende de la prioridad de los elementos. El elemento con mayor prioridad se moverá al principio de la cola. Si eliminas (sirves) el elemento mejor clasificado, el segundo va a la cabeza a buscar su café. ¿Cómo se determina la prioridad? De acuerdo con la documentación, los elementos de la cola de prioridad se ordenan según su ordenación natural o mediante un Comparador proporcionado en el momento de la construcción de la cola, según el constructor que se utilice. Una cola de prioridad basada en un montón mínimo de prioridad. Eso significa que, en el caso de elementos de cola de números, el primer elemento de la cola será el mínimo de estos números. Muy a menudo, después de leer esta definición, los estudiantes novatos comienzan a pensar que la cola de prioridad se ordena en un sentido lineal. Es decir, si, por ejemplo, usamos una cola cuyos elementos son números naturales, entonces el primer elemento será el más pequeño y el último, el más grande. Esto no es enteramente verdad. Para comprender cómo funciona realmente la cola de prioridad y lo que ofrece, debe averiguar cómo funciona el montón. Consideraremos la estructura interna de la cola de prioridad utilizando un ejemplo un poco más adelante. Ahora vamos a detenernos en sus atributos externos. entonces el primer elemento será el más pequeño y el último, el más grande. Esto no es enteramente verdad. Para comprender cómo funciona realmente la cola de prioridad y lo que ofrece, debe averiguar cómo funciona el montón. Consideraremos la estructura interna de la cola de prioridad utilizando un ejemplo un poco más adelante. Ahora vamos a detenernos en sus atributos externos. entonces el primer elemento será el más pequeño y el último, el más grande. Esto no es enteramente verdad. Para comprender cómo funciona realmente la cola de prioridad y lo que ofrece, debe averiguar cómo funciona el montón. Consideraremos la estructura interna de la cola de prioridad utilizando un ejemplo un poco más adelante. Ahora vamos a detenernos en sus atributos externos.

Declaración y constructores de la clase PriorityQueue

La clase PriorityQueue proporciona 6 formas diferentes de construir una cola de prioridad en Java.

• PriorityQueue(): cola vacía con la capacidad inicial predeterminada (11) que ordena sus elementos según su orden natural.
• PriorityQueue (Colección c): cola vacía que contiene los elementos de la colección especificada.
• PriorityQueue(int initialCapacity): cola vacía con la capacidad inicial especificada que ordena sus elementos según su orden natural.
• PriorityQueue(int initialCapacity, Comparator comparador): cola vacía con la capacidad inicial especificada que ordena sus elementos de acuerdo con el comparador especificado.
• PriorityQueue(PriorityQueue c) - cola vacía que contiene los elementos en la cola de prioridad especificada.
• PriorityQueue(SortedSet c) - cola vacía que contiene los elementos en el conjunto ordenado especificado.

Priority Queue en Java se declara de la siguiente manera:

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

Creación de PriorityQueue

Vamos a crear una cola de prioridad de enteros. Implementación de Priority Queue, código Java:

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

Hemos creado una cola de prioridad sin argumentos. En este caso, la cabeza de la cola de prioridad es el número mínimo de la cola. Si quita la cabeza, el siguiente elemento más pequeño ocupará este lugar. De modo que puede eliminar elementos de la cola en orden ascendente. Si es necesario, puede cambiar el principio de pedido utilizando la interfaz Comparator.

Métodos Java PriorityQueue

La clase PriorityQueue Java tiene métodos importantes para agregar, eliminar y verificar elementos.

Insertar elementos en la cola de prioridad

• boolean add(objeto) inserta el elemento especificado en la cola de prioridad. Devuelve verdadero en caso de éxito. Si la cola está llena, el método lanza una excepción.
• oferta booleana (objeto) inserta el elemento especificado en esta cola de prioridad. Si la cola está llena, el método devuelve falso.

Puede usar ambas operaciones de suma, no hay diferencias para la mayoría de los casos. Aquí hay un pequeño ejemplo de iniciación y adición de elementos a la cola de prioridad.

import java.util.PriorityQueue;
import java.util.Queue;
public class Priority2 {
    public static void main(String[] args) {
        Queue<Integer> priorityQueue1 = new PriorityQueue<>();
        for (int i = 5; i > 0; i--) {
            priorityQueue1.add(i);
        }
        System.out.println(priorityQueue1);
    priorityQueue1.offer(0);
        System.out.println(priorityQueue1);
    }
}

La salida es:

[1, 2, 4, 5, 3]
[0, 2, 1, 5, 3, 4]

El orden de los elementos parece ser extraño, lo explicaremos más adelante.

Recuperación y eliminación de elementos de la cola de prioridad

• boolean remove(object) elimina una sola instancia del elemento especificado de esta cola, si está presente.
• Object poll() recupera y elimina el encabezado de esta cola. Devuelve nulo si la cola está vacía.
• void clear() elimina todos los elementos de la cola de prioridad.
• Object element() recupera el encabezado de esta cola sin eliminarlo. Lanza NoSuchElementException si la cola está vacía.
• Object peek() recupera el encabezado de la cola sin eliminarlo. Devuelve nulo si la cola está vacía.

import java.util.PriorityQueue;
import java.util.Queue;
 
public class Priority2 {
    public static void main(String[] args) {
        Queue<Integer> priorityQueue = new PriorityQueue<>();
        //put 5 elements to the queue using add
        for (int i = 5; i > 0; i--) {
            priorityQueue.add(i);
        }
        System.out.println("the head of the queue = " + priorityQueue.peek());
        //removing element by element from the queue using poll and print it out
        while (!priorityQueue.isEmpty()) {
            System.out.println(priorityQueue.poll());
        }
        //put 5 new elements into the empty queue using offer
        for (int i = 10; i > 5; i--) {
            priorityQueue.offer(i);
        }
        System.out.println("now the head of the queue = " + priorityQueue.peek());
        System.out.println("the queue before removing 9:");
        System.out.println(priorityQueue);
        priorityQueue.remove(9);
        System.out.println("the queue after removing 9:");
        System.out.println(priorityQueue);
        //removing all the elements from the queue
        priorityQueue.clear();
        System.out.println(priorityQueue);
        //trying to print out the head of the empty Queue using peek - we'll get null
        System.out.println(priorityQueue.peek());
        //trying to print out the head of the empty Queue using element - we'll get the exception
        System.out.println(priorityQueue.element());
    }
}

La salida:

the head of the queue = 1
1
2
3
4
5
now the head of the queue = 6
the queue before removing 9:
[6, 7, 9, 10, 8]
the queue after removing 9:
[6, 7, 8, 10]
[]
null
Exception in thread "main" java.util.NoSuchElementException
  at java.base/java.util.AbstractQueue.element(AbstractQueue.java:136)
  at Priority2.main(Priority2.java:32)

Como puede ver, tratar de imprimir el encabezado de la Cola vacía usando el método element() conduce a NoSuchElementexception .

Comparador PriorityQueue

• Comparator comparator() devuelve el comparador que se utilizó para ordenar los elementos en la cola. Devuelve nulo si la cola se ordena según el orden natural de sus elementos.

Cola de prioridad de Java, ejemplo con comparador

Usamos el orden natural (ascendente) en los ejemplos de código anteriores, pero a veces debemos cambiarlo. Este es un ejemplo de cola de prioridad de Java, donde creamos nuestra propia clase de comparador interno que implementa la interfaz Comparator. Nuestro comparador ordenará los elementos de mayor a menor.

import java.util.PriorityQueue;
import java.util.Comparator;
 
class Priority3 {
    public static void main(String[] args) {
        // Creating a priority queue with myComparator
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new MyComparator());
        for (int i = 5; i > 0; i--) {
            priorityQueue.add(i);
        }
        System.out.println("the head of Queue = " + priorityQueue.peek());
        while (!priorityQueue.isEmpty()) {
            System.out.println(priorityQueue.poll());
        }
    }
}
 
class MyComparator implements Comparator<Integer> {
    @Override
    public int compare(Integer number1, Integer number2) {
        int value = number1.compareTo(number2);
        //sorting elements from maximal to minimal
        if (value > 0) {
            return -1;
        } else if (value < 0) {
            return 1;
        } else {
            return 0;
        }
    }
}

La salida:

the head of Queue = 5
5
4
3
2
1

El encabezado de Queue ahora no es el elemento mínimo, sino el máximo, y el orden se cambió a inverso.

Iterando sobre PriorityQueue usando iterador

ProrityQueue es parte del marco de la colección e implementa la interfaz Iterable<> . Para iterar sobre elementos de una cola de prioridad, puede usar el método iterator() . Aquí hay un ejemplo:

import java.util.PriorityQueue;
import java.util.Iterator;
import java.util.Queue;
 
class Priority4 {
   public static void main(String[] args) {
       // Creating a priority queue
       Queue<Integer> priorityQueue = new PriorityQueue<>();
       //put 5 elements to the queue using add
       for (int i = 5; i > 0; i--) {
           priorityQueue.add(i);
       }
       //Iterating via iterator() method
       Iterator<Integer> iterator = priorityQueue.iterator();
       while (iterate.hasNext()) {
           System.out.print(iterator.next() + " ");
       }
   }
}

La salida:

1 2 4 5 3 

Más métodos PriorityQueue

• boolean contains(Object o) devuelve verdadero si la cola contiene el elemento o.
• int size() devuelve el número de elementos en esta cola.
• Object[] toArray() devuelve una matriz que contiene todos los elementos de esta cola.

Aquí hay un ejemplo:

import java.util.PriorityQueue;
import java.util.Queue;
 
public class Priority5 {
   public static void main(String[] args) {
       Queue<Integer> priorityQueue = new PriorityQueue<>();
       for (int i = 5; i > 0; i--) {
           priorityQueue.offer(i);
       }
 
       System.out.println("our queue: " + priorityQueue);
 
       System.out.println("Does our queue contain 8?  " + priorityQueue.contains(8));
       System.out.println("Does queue contain 5?  " + priorityQueue.contains(5));
 
       System.out.println("The quantity of queue elements: " + priorityQueue.size());
       Object[] myArray = priorityQueue.toArray();
       System.out.println("print out our array:");
       for (Object name : myArray) {
           System.out.println(name);
       }
   }
}

La salida:

our queue: [1, 2, 4, 5, 3]
Does our queue contain 8?  false
Does our queue contain 5?  true
The quantity of queue elements: 5
print out our array:
1
2
4
5
3

PriorityQueue Definición de Java 8

Si abre la documentación de java 8 de la cola de prioridad, encontrará allí la siguiente definición: una cola de prioridad ilimitada basada en un montón de prioridad. Los elementos de la cola de prioridad se ordenan según su ordenación natural o mediante un Comparador proporcionado en el momento de la construcción de la cola, según el constructor que se utilice. Una cola de prioridad no permite elementos nulos. Una cola de prioridad que se basa en el orden natural tampoco permite la inserción de objetos no comparables (si lo hace, puede generar ClassCastException). Heap es una palabra muy importante aquí. Explica las propiedades del orden de los elementos de Priority Queue.

El principio del trabajo PriorityQueue: Binary Heap

Comencemos con un ejemplo. Vamos a crear dos objetos que implementen la interfaz Queue. Uno de ellos LinkedList, el segundo — PriorityQueue. Ambos tienen 5 elementos de Integer (1,2,3,4 y 5) y comenzamos a poner los elementos en nuestras colas desde el más grande hasta el más pequeño. Entonces, el primero sale 5, luego 4, 3, 2 y el último será 1. Luego imprima ambas listas para verificar el orden.

   Queue<Integer> queueL = new LinkedList<>();
       for (int i = 5; i > 0; i--) {
           queueL.add(i);
       }
       System.out.println("LinkedList Queue (FIFO): " + queueL);
       Queue<Integer> priorityQueue = new PriorityQueue<>();
 
       for (int i = 5; i > 0; i--) {
       priorityQueue.offer(i);
       }
       System.out.println("PriorityQueue: " + priorityQueue)

El resultado del funcionamiento de este código es el siguiente:

LinkedList Queue (FIFO): [5, 4, 3, 2, 1]
PriorityQueue: [1, 2, 4, 5, 3]

Bueno, el orden de las listas enlazadas es predecible y comprensible. Se ordena según el principio FIFO. Comenzamos con 5, por lo que este elemento es el primero en la fila, luego va 4 y así sucesivamente. ¿Qué podemos decir sobre el orden de cola de prioridad? Docs dijo que los elementos de la cola de prioridad se ordenan de acuerdo con su orden natural, o por un comparador proporcionado en el momento de la construcción de la cola. Sin embargo, este orden no parece ser "natural" en el sentido de clasificación lineal. Preferimos esperar [1, 2, 3, 4, 5], no [1, 2, 4, 5, 3]. Para comprender por qué el orden de recuperación es como es, debemos recordar esa cola de prioridad basada en un montón. ¿Qué es el montón? Es una estructura de datos basada en un árbol binario.. La propiedad principal del montón: la prioridad de cada padre es mayor que las prioridades de sus hijos. Permítanme recordarles que un árbol se llama binario completo si cada padre no tiene más de dos hijos, y el llenado de los niveles va de arriba a abajo (desde el mismo nivel, de izquierda a derecha). El montón binario se reorganiza cada vez que se agregan o eliminan elementos. En el caso de min-heap, el elemento más pequeño va a la raíz sin importar el orden de su inserción. Cola de prioridad basada en este montón mínimo. Eso significa que, en el caso de elementos de cola de números, el primer elemento de la cola será el mínimo de estos números. Si elimina la raíz, la siguiente más pequeña se convierte en una raíz.

Volvamos a nuestro ejemplo.

Paso 1. Ponemos '5' en la cola de prioridad. Se convierte en raíz. Paso 2. Agregamos '4' a la cola de prioridad. 4 <5, por lo que el nuevo elemento debe ser más alto que el anterior. El 4 se convierte en raíz, el 5 es su hijo izquierdo. Ahora la estructura de datos en Java es [4, 5] Paso 3. Agregamos '3'. Temporalmente se convierte en hijo derecho de una raíz (4). Sin embargo, 3 < 4, entonces deberíamos levantarlo. Intercambia 3 y 4. Ahora tenemos una estructura como [3, 5, 4] Paso 4. Agregamos '2'. Se convierte en un hijo izquierdo de 5. 2<5, así que cámbielos. 2 se convierte en un hijo izquierdo de 3, 2 < 3, así que un proceso de intercambio más. Ahora tenemos una estructura [2,3,4,5] Paso 5.Agregamos '1'. Viene del hijo derecho del 3 al hijo izquierdo del 2, y luego va a la raíz. La estructura de datos resultante: [1,2,4,5,3] El proceso de eliminación comienza desde una raíz y provoca los procedimientos inversos. Entonces, primero tenemos 1 como raíz, luego 2, 3, 4 y por último 5. Es por eso que usar la operación de eliminación poll()

while (!priorityQueue.isEmpty()) {
           System.out.println(priorityQueue.poll());
       }

tenemos "ordenados" en la salida de sentido lineal:

1
2
3
4
5

Entonces, la cola de prioridad podría ser efectiva para algunas operaciones. Se necesita tiempo O (log N) para insertar y eliminar cada elemento, y puede obtener el elemento mínimo en O (1). Aquí está el ejemplo completo:

import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
 
public class PriorityQueueExample {
   public static void main(String[] args) {
 
       Queue<Integer> queueL = new LinkedList<>();
       for (int i = 5; i > 0; i--) {
           queueL.add(i);
       }
       System.out.println("Print our LinkedList Queue (FIFO): " + queueL);
       Queue<Integer> priorityQueue = new PriorityQueue<>();
 
       for (int i = 5; i > 0; i--) {
       priorityQueue.offer(i);
       }
 
       System.out.println("PriorityQueue printing (by iterating, no elements removing): " + priorityQueue);
       System.out.println("Print PriorityQueue using poll() (by retrieval): " );
       while (!priorityQueue.isEmpty()) {
           System.out.println(priorityQueue.poll());
       }
}
}
Print our LinkedList Queue (FIFO): [5, 4, 3, 2, 1]
PriorityQueue printing (by iterating, no elements removing): [1, 2, 4, 5, 3]
Print our  PriorityQueue using poll() (by retrieval): 
1
2
3
4
5

Es importante comprender que las colas de prioridad se basan en montones binarios, por lo que no mantienen los elementos en un orden ordenado lineal. Todos los caminos desde la raíz hasta la hoja están ordenados, pero los diferentes caminos desde la raíz no lo están. Eso significa que puede obtener el elemento mínimo de la cola muy rápidamente.

Lo que debe saber sobre la cola de prioridad. Breve lista

• Priority Queue no permite objetos NULL.
• Solo puede agregar objetos comparables a PriorityQueue.
• La cola de prioridad se crea como un montón mínimo, una especie de árbol binario. El elemento mínimo es una raíz. Los objetos de la cola de prioridad se ordenan por defecto en orden natural.
• Puede usar Comparator si necesita un pedido personalizado.
• PriorityQueue no es seguro para subprocesos, por lo que es mejor que utilice PriorityBlockingQueue para trabajar en un entorno concurrente.
• PriorityQueue proporciona tiempo O(log(n)) para agregar y sondear métodos y O(1) para obtener elementos mínimos.