Se utiliza PriorityQueue cuando se supone que los objetos deben procesarse según la prioridad. Se sabe que un Cola Sigue el algoritmo First-In-First-Out, pero a veces es necesario 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 prioridades. Los elementos de la cola de prioridad se ordenan según el orden 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 siguiente cola de prioridad, un elemento con un valor ASCII máximo tendrá la prioridad más alta.
Declaración:
public class PriorityQueue extends AbstractQueue implements Serializable where E is the type of elements held in this queue>
La clase implementa Serializable , iterable , Recopilación , Cola interfaces.
Algunos puntos importantes sobre la cola de prioridad son como sigue:
- PriorityQueue no permite valores nulos.
- No podemos crear una PriorityQueue de objetos que no sean comparables
- PriorityQueue son colas independientes.
- El encabezado de esta cola es el elemento menor con respecto al orden especificado. Si varios elementos están empatados por el menor valor, 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 multiproceso de Java.
- Las operaciones de recuperación de la cola sondean, eliminan, miran y acceden al elemento que se encuentra al principio de la cola.
- Proporciona tiempo O(log(n)) para métodos de adición y sondeo.
- Hereda métodos de ResumenCola , Colección abstracta , Recopilación, y Objeto clase.
Constructores:
1. Cola de prioridad (): Crea una PriorityQueue con la capacidad inicial predeterminada (11) que ordena sus elementos según su orden natural.
PriorityQueue pq = nueva PriorityQueue();
2. PriorityQueue (Colección c): Crea una PriorityQueue que contiene los elementos de la colección especificada.
PriorityQueue pq = new PriorityQueue (Colección c);
3. PriorityQueue (int capacidad inicial) : Crea una PriorityQueue con la capacidad inicial especificada que ordena sus elementos según su orden natural.
PriorityQueue pq = new PriorityQueue(int capacidadinicial);
4. PriorityQueue (int capacidad inicial, comparador comparador): Crea una PriorityQueue con la capacidad inicial especificada que ordena sus elementos según el comparador especificado.
PriorityQueue pq = new PriorityQueue (int capacidad inicial, comparador comparador);
5. Cola de prioridad (Cola de prioridad c) : Crea una PriorityQueue que contiene los elementos de la cola de prioridad especificada.
PriorityQueue pq = new PriorityQueue(PriorityQueue c);
6. Cola de prioridad (Conjunto ordenado c) : Crea una PriorityQueue que contiene los elementos del conjunto ordenado especificado.
PriorityQueue pq = new PriorityQueue (SortedSet c);
7. PriorityQueue(Comparador comparador): Crea una PriorityQueue con la capacidad inicial predeterminada y cuyos elementos están ordenados según el comparador especificado.
PriorityQueue pq = new PriorityQueue(Comparador c);
Ejemplo:
El siguiente ejemplo explica las siguientes operaciones básicas de la cola de prioridad.
convención de nomenclatura para java
- boolean add (elemento E): este método inserta el elemento especificado en esta cola de prioridad.
- public peek(): este método recupera, pero no elimina, el encabezado de esta cola, o devuelve nulo si esta cola está vacía.
- encuesta pública(): este método recupera y elimina el encabezado de esta cola, o devuelve nulo si esta cola está vacía.
Java
// 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 pQueue =>new> PriorityQueue();> >// 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());> >}> }> |
>
>Producción
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 orden de inserción no se conserva en PriorityQueue. Los elementos se almacenan según el orden de prioridad que es ascendente por defecto.
Java
/*package whatever //do not write package name here */> import> java.util.*;> import> java.io.*;> > public> class> PriorityQueueDemo {> > >public> static> void> main(String args[])> >{> >PriorityQueue pq =>new> PriorityQueue();> >for>(>int> i=>0>;i<>3>;i++){> >pq.add(i);> >pq.add(>1>);> >}> >System.out.println(pq);> >}> }> |
>
>Producción
[0, 1, 1, 1, 2, 1]>
No obtendremos elementos ordenados imprimiendo PriorityQueue.
Java
/*package whatever //do not write package name here */> import> java.util.*;> import> java.io.*;> > public> class> PriorityQueueDemo {> > >public> static> void> main(String args[])> >{> >PriorityQueue pq =>new> PriorityQueue();> > >pq.add(>'Geeks'>);> >pq.add(>'For'>);> >pq.add(>'Geeks'>);> > >System.out.println(pq);> >}> }> |
>
>Producción
[For, Geeks, Geeks]>
2. Eliminación de elementos: Para eliminar un elemento de una cola de prioridad, podemos utilizar el método remove(). Si hay varios objetos de este tipo, se elimina la primera aparición del objeto. Aparte de eso, el método poll() también se utiliza para quitar la cabeza y devolverla.
Java
// Java program to remove elements> // from a PriorityQueue> import> java.util.*;> import> java.io.*;> public> class> PriorityQueueDemo {> >public> static> void> main(String args[])> >{> >PriorityQueue 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);> >}> }> |
>
>Producción
Initial PriorityQueue [For, Geeks, Geeks] After Remove - [For, Geeks] Poll Method - For Final PriorityQueue - [Geeks]>
3. Accediendo a los elementos: Dado que la cola sigue el principio de primero en entrar, primero en salir, solo podemos acceder al encabezado de la cola. Para acceder a elementos de una cola prioritaria, podemos utilizar el método peek().
negrita el texto en css
Java
// 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 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);> >}> }> |
>
>Producción
PriorityQueue: [For, Geeks, Geeks] Accessed Element: For>
4. Iterando PriorityQueue: Hay varias formas de iterar a través de PriorityQueue. La forma más famosa es convertir la cola en una matriz y recorrerla utilizando el bucle for. Sin embargo, la cola también tiene un iterador incorporado que se puede utilizar para iterar a través de la cola.
Java
// Java program to iterate elements> // to a PriorityQueue> import> java.util.*;> public> class> PriorityQueueDemo {> >// Main Method> >public> static> void> main(String args[])> >{> >PriorityQueue pq =>new> PriorityQueue();> >pq.add(>'Geeks'>);> >pq.add(>'For'>);> >pq.add(>'Geeks'>);> >Iterator iterator = pq.iterator();> >while> (iterator.hasNext()) {> >System.out.print(iterator.next() +>' '>);> >}> >}> }> |
>
>Producción
For Geeks Geeks>
Ejemplo:
Java
import> java.util.PriorityQueue;> public> class> PriorityQueueExample {> >public> static> void> main(String[] args) {> > >// Create a priority queue with initial capacity 10> >PriorityQueue pq =>new> PriorityQueue(>10>);> > >// Add elements to the queue> >pq.add(>3>);> >pq.add(>1>);> >pq.add(>2>);> >pq.add(>5>);> >pq.add(>4>);> > >// Print the queue> >System.out.println(>'Priority queue: '> + pq);> > >// Peek at the top element of the queue> >System.out.println(>'Peek: '> + pq.peek());> > >// Remove the top element of the queue> >pq.poll();> > >// Print the queue again> >System.out.println(>'Priority queue after removing top element: '> + pq);> > >// Check if the queue contains a specific element> >System.out.println(>'Does the queue contain 3? '> + pq.contains(>3>));> > >// Get the size of the queue> >System.out.println(>'Size of queue: '> + pq.size());> > >// Remove all elements from the queue> >pq.clear();> > >// Check if the queue is empty> >System.out.println(>'Is the queue empty? '> + pq.isEmpty());> >}> }> |
>
>Producción
Priority queue: [1, 3, 2, 5, 4] Peek: 1 Priority queue after removing top element: [2, 3, 4, 5] Does the queue contain 3? true Size of queue: 4 Is the queue empty? true>
Ejemplos en tiempo real:
La cola de prioridad es una estructura de datos en la que los elementos están ordenados por prioridad, y los elementos de mayor prioridad aparecen al principio de la cola. A continuación se muestran algunos ejemplos del mundo real de dónde se pueden utilizar colas de prioridad:
- Programación de tareas: en los sistemas operativos, las colas de prioridad se utilizan para programar tareas en función de sus niveles de prioridad. Por ejemplo, una tarea de alta prioridad, como una actualización crítica del sistema, se puede programar antes que una tarea de menor prioridad, como un proceso de copia de seguridad en segundo plano. Sala de emergencias: en la sala de emergencias de un hospital, los pacientes son clasificados según la gravedad de su afección, y los que se encuentran en estado crítico reciben tratamiento primero. Se puede utilizar una cola de prioridad para gestionar el orden en que los médicos y enfermeras atienden a los pacientes. Enrutamiento de red: en las redes informáticas, las colas de prioridad se utilizan para gestionar el flujo de paquetes de datos. A los paquetes de alta prioridad, como los datos de voz y vídeo, se les puede dar prioridad sobre los datos de menor prioridad, como el correo electrónico y las transferencias de archivos. Transporte: en los sistemas de gestión del tráfico, se pueden utilizar colas prioritarias para gestionar el flujo del tráfico. Por ejemplo, a los vehículos de emergencia, como las ambulancias, se les puede dar prioridad sobre otros vehículos para garantizar que puedan llegar a su destino rápidamente. Programación de trabajos: en los sistemas de programación de trabajos, las colas de prioridad se pueden utilizar para gestionar el orden en que se ejecutan los trabajos. Los trabajos de alta prioridad, como las actualizaciones críticas del sistema, se pueden programar antes que los trabajos de menor prioridad, como las copias de seguridad de datos. Mercados en línea: en los mercados en línea, las colas de prioridad se pueden utilizar para gestionar la entrega de productos a los clientes. Los pedidos de alta prioridad, como el envío exprés, pueden tener prioridad sobre los pedidos de envío estándar.
En general, las colas de prioridad son una estructura de datos útil para gestionar tareas y recursos en función de sus niveles de prioridad en varios escenarios del mundo real.
Métodos en la clase PriorityQueue
| MÉTODO | DESCRIPCIÓN |
|---|---|
| agregar(Y y) | Inserta el elemento especificado en esta cola de prioridad. |
| claro() | Elimina todos los elementos de esta cola de prioridad. |
| comparador() | Devuelve el comparador utilizado para ordenar los elementos de esta cola, o nulo si esta cola está ordenada según el orden natural de sus elementos. |
| contiene?(Objeto o) | Devuelve verdadero si esta cola contiene el elemento especificado. |
| ¿Para cada uno? (Acción del consumidor) | Realiza la acción dada para cada elemento del Iterable hasta que se hayan procesado todos los elementos o la acción genere una excepción. |
| iterador() | Devuelve un iterador sobre los elementos de esta cola. |
| oferta?(E e) | Inserta el elemento especificado en esta cola de prioridad. |
| ¿eliminar? (Objeto o) | Elimina una única instancia del elemento especificado de esta cola, si está presente. |
| ¿eliminar todo? (Colección c) | Elimina todos los elementos de esta colección que también están contenidos en la colección especificada (operación opcional). |
| removeIf?(Filtro de predicado) | Elimina todos los elementos de esta colección que satisfacen el predicado dado. |
| ¿retener todo? (Colección c) | Conserva solo los elementos de esta colección que están contenidos en la colección especificada (operación opcional). |
| divisor() | Crea un Spliterator de enlace tardío y a prueba de fallos sobre los elementos de esta cola. |
| a matriz() | Devuelve una matriz que contiene todos los elementos de esta cola. |
| aArray?(T[]a) | Devuelve una matriz que contiene todos los elementos de esta cola; el tipo de tiempo de ejecución de la matriz devuelta es el de la matriz especificada. |
Métodos declarados en la clase java.util.AbstractQueue
| MÉTODO | DESCRIPCIÓN |
|---|---|
| agregarTodo(Colección c) | Agrega todos los elementos de la colección especificada a esta cola. |
| elemento() | Recupera, pero no elimina, el encabezado de esta cola. |
| eliminar() | Recupera y elimina el encabezado de esta cola. |
Métodos declarados en la clase java.util.AbstractCollection
| MÉTODO | DESCRIPCIÓN |
|---|---|
| contieneTodo(Colección c) | Devuelve verdadero si esta colección contiene todos los elementos de la colección especificada. |
| esta vacio() | Devuelve verdadero si esta colección no contiene elementos. |
| Encadenar() | Devuelve una representación de cadena de esta colección. |
Métodos declarados en la interfaz java.util.Collection
| MÉTODO | DESCRIPCIÓN |
|---|---|
| contieneTodo(Colección c) | Devuelve verdadero si esta colección contiene todos los elementos de la colección especificada. |
| es igual(Objeto o) | Compara el objeto especificado con esta colección para determinar la igualdad. |
| código hash() | Devuelve el valor del código hash para esta colección. |
| esta vacio() | Devuelve verdadero si esta colección no contiene elementos. |
| corriente paralela() | Devuelve un Stream posiblemente paralelo con esta colección como fuente. |
| tamaño() | Devuelve el número de elementos de esta colección. |
| arroyo() | Devuelve un Stream secuencial con esta colección como origen. |
| toArray (generador de funciones internas) | Devuelve una matriz que contiene todos los elementos de esta colección, utilizando la función generadora proporcionada para asignar la matriz devuelta. |
Métodos declarados en la interfaz java.util.Queue
| MÉTODO | DESCRIPCIÓN |
|---|---|
| ojeada() | Recupera, pero no elimina, el encabezado de esta cola, o devuelve nulo si esta cola está vacía. |
| encuesta() | Recupera y elimina el encabezado de esta cola, o devuelve nulo si esta cola está vacía. |
Aplicaciones :
- Implementación de los algoritmos de Dijkstra y Prim.
- Maximizar la suma de la matriz después de K negaciones
Artículos relacionados :
- Clase Java.util.PriorityQueue en Java
- Implementar PriorityQueue a través de Comparator en Java