java priority queue tutorial implementation examples
Este tutorial explica la cola de prioridad de Java y conceptos relacionados como comparador, cola de prioridad mínima y máxima junto con su implementación con ejemplos:
La estructura de datos de Priority Queue es una cola especial en la que los elementos están presentes no según el orden FIFO, sino según los elementos naturales o cualquier comparador personalizado utilizado durante la creación de la cola.
=> Eche un vistazo a la guía para principiantes de Java aquí.
Lo que vas a aprender:
Cola de prioridad en Java
En Priority Queue, la parte delantera de la cola tiene la menor cantidad de elementos según el orden natural y la parte trasera apunta al elemento más grande de la cola.
A continuación se muestra un ejemplo de cola de prioridad que consta de números.
prueba unitaria prueba de integración prueba del sistema
Por lo tanto, cuando un elemento se elimina de la cola de prioridad que se muestra arriba, será el elemento menor.
De manera similar, para una cola de prioridad alfabética, se considerarán los valores ASCII y los elementos de la cola se ordenarán según los valores ASCII.
A continuación se enumeran algunas de las principales características de PriorityQueue:
- PriorityQueue es una cola independiente.
- PriorityQueue no permite valores nulos.
- Para objetos no comparables, no podemos crear una cola de prioridad.
- PriorityQueue hereda de clases como AbstractQueue, AbstractCollection, Collection y Object.
- El encabezado o el frente de la cola contiene el menor elemento según el orden natural.
- La implementación de Priority Queue no es segura para subprocesos. Por lo tanto, si deseamos un acceso sincronizado, debemos usar PriorityBlockingQueue.
La clase PriorityQueue hereda la interfaz de cola de Java y es parte del paquete java.util.
La declaración general de la clase PriorityQueue se da a continuación:
|_+_|El siguiente diagrama muestra la jerarquía de clases para la clase PriorityQueue.
Complejidad de tiempo de la cola de prioridad
- La complejidad de tiempo de Priority Queue para los métodos de inserción (enqueue) y eliminación (dequeue) es O (log (n)).
- Priority Queue tiene una complejidad de tiempo lineal para eliminar y contiene métodos.
- Los métodos que recuperan elementos de la cola de prioridad tienen una complejidad de tiempo constante.
Ejemplo de cola de prioridad en Java
El siguiente programa demuestra un PriorityQueue simple en Java. Creamos un objeto de la clase PriorityQueue, le agregamos valores y luego mostramos el contenido de la cola usando Iterator.
|_+_|Producción:
Métodos de API de cola de prioridad de Java
Constructores:
| Prototipo de constructor | Descripción | |
|---|---|---|
| ojeada | E mirar () | Devuelve el encabezado de la cola sin eliminar el elemento. |
| PriorityQueue() | Un constructor predeterminado que crea un objeto PriorityQueue con capacidad inicial como 1. | |
| PriorityQueue (colección c) | Crea un objeto PriorityQueue con elementos iniciales de la colección dada c. | |
| PriorityQueue (int initialCapacity) | Crea un objeto PriorityQueue con la 'capacidad inicial' dada. Los elementos se ordenan según el orden natural. | |
| PriorityQueue (int initialCapacity, comparador comparador) | Crea un objeto PriorityQueue con la 'capacidad inicial' dada. Los elementos están ordenados según el comparador dado. | |
| PriorityQueue( PriorityQueue c ) | Crea un objeto PriorityQueue a partir de otro objeto PriorityQueue dado por c. | |
| PriorityQueue (SortedSet c) | Crea un objeto PriorityQueue a partir de un SortedSet dado por c. |
Métodos
| Método | Prototipo de método | Descripción |
|---|---|---|
| agregar | suma booleana (E e) | Agrega el elemento e a PriorityQueue. |
| claro | vacío claro () | Limpia PriorityQueue eliminando todos los elementos. |
| comparador | Comparatorcomparator() | Devuelve un comparador personalizado que se utiliza para ordenar los elementos de la cola. |
| contiene | booleano contiene (Objeto o) | Comprueba si PriorityQueue contiene el elemento dado o. Devuelve verdadero si es así. |
| iterador | Iteratoriterator () | Método para obtener un iterador para el PriorityQueue dado. |
| oferta | oferta booleana (E e) | Inserte el elemento e dado en PriorityQueue. |
| encuesta | Encuesta E () | Elimina y devuelve el encabezado de la cola. Devuelve nulo si la cola está vacía. |
| retirar | booleano eliminar (Objeto o) | Elimina una instancia de un elemento dado o si está presente en la cola. |
| Talla | int tamaño () | Devuelve el tamaño o la cantidad de elementos de esta PriorityQueue. |
| toArray | Objeto () toArray () | Devuelve una representación de matriz del PriorityQueue dado. |
| toArray | T () toArray (T () a) | Devuelve una representación de matriz para la Cola de prioridad dada con el mismo tipo de tiempo de ejecución que la matriz especificada a. |
Implementación en Java
Demostremos los métodos anteriores de PriorityQueue utilizando un programa Java.
|_+_|Producción:
mejor aplicación espía para celular
Cola de prioridad en Java 8
Java 8 agrega un método más a la clase PriorityQueue, es decir, 'spliterator ()'.
Los detalles de este método se dan a continuación.
Nombre del método: disidente
Prototipo de método: spliterator spliterator final público ()
Descripción del método: Este método crea un spliterator sobre los elementos PriorityQueue. Este separador es de enlace tardío y rápido.
Comparador de cola de prioridad
Como ya se mencionó, los elementos PriorityQueue están ordenados de forma natural. Si queremos cambiar el orden, debemos especificar un comparador y usarlo durante la creación del objeto PriorityQueue. PriorityQueue luego usa este comparador para ordenar sus elementos.
El siguiente programa Java demuestra el uso de un comparador personalizado para ordenar elementos. En este programa, definimos un nuevo comparador personalizado dentro del cual anulamos el método 'comparar'. El método de comparación se utiliza para ordenar los elementos de PriorityQueue según la longitud.
|_+_|Producción:
Cola de prioridad mínima en Java
El orden natural de Priority Queue tiene el elemento más pequeño o más pequeño al principio de la cola y, por lo tanto, el orden es ascendente. Esto se denomina 'cola de prioridad mínima' con un orden ascendente de elementos.
El programa Java a continuación muestra la implementación de la cola de prioridad mínima en Java.
|_+_|Producción:
Cola de prioridad máxima en Java
Mientras que la cola de prioridad mínima tiene elementos en orden ascendente, la cola de prioridad máxima tiene los elementos en orden descendente, es decir, el encabezado de la cola de prioridad máxima devolverá el elemento más grande en la cola.
El siguiente programa Java demuestra la cola de prioridad máxima en Java.
mejor limpiador de sistema gratuito para windows 10|_+_|
Producción:
Como se muestra en el programa anterior, para cambiar el orden natural de los elementos en la cola de prioridad, tenemos que definir un comparador personalizado.
Preguntas frecuentes
P # 1) ¿Qué es la cola de prioridad en Java?
Responder: Una cola especial en la que todos los elementos de la cola se ordenan según el orden natural o utilizando un comparador personalizado se denomina cola de prioridad. No sigue el orden FIFO.
P # 2) ¿Cómo se configura una cola de prioridad máxima en Java?
Responder: Podemos establecer una cola de prioridad máxima en Java usando un comparador personalizado para que el jefe de la cola devuelva el elemento más grande en la cola.
P # 3) ¿La cola de prioridad permite duplicados de Java?
Responder: Si. Priority Queue permite valores duplicados.
P # 4) ¿La cola de prioridad de Java es máxima o mínima?
Responder: De forma predeterminada, la cola de prioridad en Java es la cola de prioridad mínima con orden natural. Para que sea máximo, tenemos que usar un comparador personalizado para que el encabezado de la cola devuelva el elemento más grande de la cola.
P # 5) ¿Está ordenada una cola de prioridad?
Responder: De forma predeterminada, el encabezado de la cola está ordenado y la cola Prioridad tiene el menor elemento como encabezado. El resto de elementos se ordena cuando se requiere.
Conclusión
Esto completa el tutorial sobre colas prioritarias en Java. Priority Queue implementa una interfaz de cola y es una cola especial donde los elementos se ordenan según el orden natural. No sigue el orden FIFO. Para cambiar el orden natural de la cola de prioridad, podemos usar el comparador personalizado.
Las colas de prioridad se utilizan principalmente para la programación de impresoras, la programación de tareas de la CPU, etc. El montón (mínimo o máximo) también se implementa mediante colas de prioridad.
=> Lea la serie de formación Easy Java.
Lectura recomendada
- Estructura de datos de cola de prioridad en C ++ con ilustración
- Cola de prioridad en STL
- Cola de Java: métodos de cola, implementación de cola con ejemplos
- Estructura de datos de cola circular C ++: implementación y aplicaciones
- Cola de doble extremo (Deque) en C ++ con ejemplos
- Estructura de datos de cola en C ++ con ilustración
- Pilas y colas en STL
- Tutorial de JAVA para principiantes: más de 100 tutoriales prácticos en vídeo de Java