Cola prioritaria en Java

Suponga que ofrece servicio a tres personas diferentes paradas frente a usted. La tercera persona es tu amigo. Se supone que el servicio está por primera vez. Con el primer servicio_first, la primera persona tiene la mayor prioridad; La segunda persona tiene la mayor prioridad; la tercera persona, la prioridad menor, y así sucesivamente. No serás castigado, si no observas a First-Come_first. Decidiste servir primero a tu amigo, luego a la primera persona, seguido por la segunda persona. Esto significa que le diste a tu amigo la mayor prioridad. Mirando el escenario desde el punto de vista de un robot, la tercera posición tenía la mayor prioridad.

Al día siguiente, vinieron las mismas tres personas. Esta vez, tu amigo está en el medio. Decidiste servirle primero, por delante de la persona que vino primero, luego la tercera persona, y finalmente, la primera persona. Entonces, esta vez, según el robot, la posición 2 tiene la mayor prioridad, seguida de la posición 3.

Al tercer día, tu amigo es el primero y lo haces por primera vez. La conclusión de cualquier persona, y el robot, es que la prioridad depende de quién está preocupado y por la posición de cada persona. NOTA: En la vida real, la prioridad no siempre depende de la primera costumbre.

En la programación, una cola de prioridad binaria es donde el primer elemento tiene la mayor prioridad. El tercer elemento puede tener la mayor prioridad, y el segundo elemento, la tercera prioridad. Las colas prioritarias son de naturaleza binaria. Nota: El primer elemento es siempre la mayor prioridad en una cola de prioridad. También puede suceder que el segundo elemento tenga una mayor prioridad y el tercer elemento tiene la tercera prioridad. En la definición de la cola prioritaria, las prioridades del segundo y tercer ítems pueden no estar en orden descendente. Esta diferencia continúa por la cola hasta el último elemento, que puede no ser el elemento de menor prioridad. Sin embargo, estará entre los de la prioridad más baja. Esta clasificación parcial también se conoce como orden parcial. Entonces, una cola de prioridad es una cola de pedidos parciales, donde la prioridad no es de primer momento, aunque esa es la regla general.

Al tratar con la matriz, First-COME_FIRST Served es First-In_First-Out, escrito como FIFO. En la computación, la cola es FIFO, mientras que la cola prioritaria es un FIFO parcial porque a medida que la cola desciende, algunos elementos tienen prioridades mayores que sus predecesores cercanos. A medida que la cola prioritaria desciende aún más, aumenta la distancia entre tales predecesores y las prioridades más altas.

Una cola prioritaria se implementa como una estructura de datos de montón. La siguiente pregunta es, ¿qué es un montón?? Existe el montón máximo y el montón mínimo, que se discutirá en detalle a continuación.

Contenido del artículo

• Estructura de datos de montón
• Cola prioritaria en Java Proper
• Construcción de Java de una cola prioritaria
• Métodos de Java de una cola prioritaria
• Conclusión

Estructura de datos de montón

Hay max-heap, y hay mín. Con Max-Heap, el primer elemento es el mayor valor. A medida que la cola desciende, los valores continúan disminuyendo, aumentando y generalmente disminuyendo. Con min-heap, el primer elemento es el valor más pequeño. A medida que la cola desciende, los valores continúan aumentando y disminuyendo y generalmente aumentan. Los valores de un montón se pueden mantener en una matriz.

Un montón binario es donde un nodo (artículo) tiene dos hijos. El primer hijo es el niño izquierdo y el segundo hijo es el niño derecho. El valor de cualquier nodo se llama clave.

Montón

La siguiente lista es un máximo de montón que ya está parcialmente ordenado y no necesita más pedidos:

89, 85, 87, 84, 82, 79, 73, 80, 81 ,, 65, 69

89 es el primer valor en el índice 0. Es el nodo raíz (padre raíz). Es el mayor valor entre todos los valores. Su primer hijo (85) está en el índice 1, cuyo índice es igual a 2 (0) + 1, donde 0 es el índice del padre. Su segundo hijo (87) está en el índice 2, que es igual a 2 (0) + 2, donde 0 es el índice del padre.

85 está en el índice 1. Es un padre. Su primer hijo (84) está en el índice 3, que es igual a 2 (1) + 1, donde 1 es el índice del padre. Su segundo hijo (82) está en el índice 4, que es igual a 2 (1) + 2, donde 1 es el índice del padre.

87 está en el índice 2. Es un padre. Su primer hijo (79) está en el índice 5, que es igual a 2 (2) + 1, donde 2 es el índice del padre. Su segundo hijo (73) está en el índice 6, que es igual a 2 (2) + 2, donde 2 es el índice del padre.

En general, a medida que el recuento de índice comienza a partir de 0, que represente el índice de un padre de la matriz; Y así, la izquierda (primero) hijo de un padre en el índice I está en el índice 2i + 1; y su niño (segundo) niño, está en el índice 2i + 2. Algunas celdas hacia el final de la matriz pueden estar vacías; No deben tener valores.

La lista anterior es un buen ejemplo del contenido de una cola prioritaria después de que se complete la inclusión de elementos. Si se elimina el primer elemento, el resto se reorganiza para que la configuración de los valores, formando una nueva cola de prioridad. De esa manera, la eliminación de todos los elementos de la parte superior aparecería como si todos los elementos estuvieran ordenados correctamente. Los elementos aún se pueden obtener como están, en un orden parcial, sin eliminar ningún elemento.

Mínimo

Min-Heap es el reverso de Max-Heap.

Cola prioritaria en Java Proper

Java tiene una clase llamada priorityqueue, para la cola de prioridad. Tiene muchos constructores y métodos. Solo se explican a continuación tres constructores y los métodos más apropiados:

Construcción de Java de una cola prioritaria

Public PriorityQueue ()

Esto crea una cola prioritaria sin ningún elemento. La clase, priorityqueue, está en la java.utilizar.* Paquete, que debe importarse. El siguiente segmento de código crea una priorityqueue vacía y luego agrega valores sin clasificar (ni siquiera parcialmente ordenados) a la cola:

Prioridad PQ = nuevo priorityqueue();
pq.agregar (69); pq.agregar (65); pq.agregar (87); pq.agregar (79);
pq.agregar (73); pq.agregar (84); pq.agregar (89); pq.agregar (80);
pq.agregar (81); pq.agregar (82); pq.agregar (85);

Estos números son todos enteros. Son de la lista parcialmente ordenada proporcionada anteriormente, pero actualmente, están completamente sin clasificar a medida que se ingresan. Los elementos en PQ ahora se clasifican parcialmente de acuerdo con la definición de la cola prioritaria en Java.

Priorityqueue público (priorityqueue c)

Esto crea una prioridad de otro priorityqueue. El siguiente segmento de código ilustra esto:

Prioridad PQ = nuevo priorityqueue();
pq.agregar (69); pq.agregar (65); pq.agregar (87); pq.agregar (79);
pq.agregar (73); pq.agregar (84); pq.agregar (89); pq.agregar (80);
pq.agregar (81); pq.agregar (82); pq.agregar (85);
Prioridad PQ1 = nuevo priorityqueue(PQ);

PQ1 ha sido creado a partir de PQ. Actualmente tiene el mismo orden parcial y PQ.

El tercer método de constructor se ilustra a continuación.

Métodos de Java de una cola prioritaria

Public int size ()

Esto devuelve el tamaño de la lista y no incluye celdas vacías, como se ilustra en el siguiente código:

Prioridad PQ = nuevo priorityqueue();
pq.agregar (69); pq.agregar (65); pq.agregar (87); pq.agregar (79);
pq.agregar (73); pq.agregar (84); pq.agregar (89); pq.agregar (80);
pq.agregar (81); pq.agregar (82); pq.agregar (85);
int sz = pq.tamaño();
Sistema.afuera.println (SZ);

La salida es 11.

Public Void foreach (acción del consumidor)

Este método debe usarse de manera especial para copiar todos los valores en la cola de prioridad en el formulario parcialmente ordenado. El siguiente programa ilustra esto:

Prioridad PQ = nuevo priorityqueue();
pq.agregar (69); pq.agregar (65); pq.agregar (87); pq.agregar (79);
pq.agregar (73); pq.agregar (84); pq.agregar (89); pq.agregar (80);
pq.agregar (81); pq.agregar (82); pq.agregar (85);
pq.foreach (elemento -> sistema.afuera.imprimir (elemento + ""));
Sistema.afuera.println ();

Tenga en cuenta la forma en que se ha realizado el código dentro de los paréntesis del método foreach. El elemento es una variable ficticia que representa cada elemento en la cola. Tenga en cuenta el uso del operador de flecha. La salida es:

65 69 84 79 73 87 89 80 81 82 85

La salida es correcta, en un orden parcial, pero en un orden ascendente. Este no es necesariamente el orden inverso dado anteriormente debido a la forma en que los valores se incluyeron en la lista. Es decir, el método foreach devuelve la lista como un mínimo-montón. Para devolver la lista en orden descendente, use el siguiente constructor:

Public PriorityQueue (comparador de comparación)

Este es un constructor. El siguiente código muestra cómo usarlo:

Prioridad PQ = nuevo priorityqueue((x, y) -> entero.comparar (y, x));
pq.agregar (69); pq.agregar (65); pq.agregar (87); pq.agregar (79);
pq.agregar (73); pq.agregar (84); pq.agregar (89); pq.agregar (80);
pq.agregar (81); pq.agregar (82); pq.agregar (85);
pq.foreach (elemento -> sistema.afuera.imprimir (elemento + ""));

Las x, y son variables ficticias que representan los valores menores y menos menos. Tenga en cuenta que en los primeros paréntesis para X e Y, X viene antes de Y. En la segunda paréntesis, Y viene antes de x. La salida es:

89 85 87 80 82 69 84 65 79 73 81

ADD PÚBLICO BOOLEAN (E E)

El número de elementos en una cola prioritaria se puede aumentar uno por uno. Este método devuelve verdadero si se produjo un cambio; y falso de lo contrario. El siguiente código agrega el duodécimo valor práctico a la cola:

Prioridad PQ = nuevo priorityqueue((x, y) -> entero.comparar (y, x));
pq.agregar (69); pq.agregar (65); pq.agregar (87); pq.agregar (79);
pq.agregar (73); pq.agregar (84); pq.agregar (89); pq.agregar (80);
pq.agregar (81); pq.agregar (82); pq.agregar (85); pq.agregar (70);
pq.foreach (elemento -> sistema.afuera.imprimir (elemento + ""));

El valor agregado avanzaría en la cola para que se ajuste a su posición apropiada, lo que lleva a un reajuste de las posiciones de los elementos. La salida es:

89 85 87 80 82 70 84 65 79 73 81 69

PUBLIC E POLL ()

Este método recupera y elimina la cabeza de la cola; o devuelve nulo, si esta cola está vacía. Cada vez que se retira la cabeza, la cola prioritaria se reajusta para tener una nueva cabeza legítima. Si la cabeza se continúa eliminando, los valores devueltos estarán en orden ordenado completo. El siguiente código ilustra esto:

Prioridad PQ = nuevo priorityqueue((x, y) -> entero.comparar (y, x));
pq.agregar (69); pq.agregar (65); pq.agregar (87); pq.agregar (79);
pq.agregar (73); pq.agregar (84); pq.agregar (89); pq.agregar (80);
pq.agregar (81); pq.agregar (82); pq.agregar (85); pq.agregar (70);
pq.foreach (elemento -> sistema.afuera.Imprimir (PQ.encuesta () + ""));

La salida de la computadora del autor es:

89 87 85 84 82 81 80 79 73 70 69 65 Excepción en el hilo "principal" Java.utilizar.ConcurrenteModificationException
en Java.base/java.utilizar.Prioridad.foreach (priorityqueue.Java: 984)
en el theclass.principal (.Java: 11)

Tenga en cuenta que la salida es de orden ordenado completo. Este código en particular no pudo detectar la excepción lanzada. Este problema se deja como un ejercicio de investigación para el lector.

Conclusión

Una cola prioritaria en Java es una cola en la que los elementos tienen prioridad más que FIFO. Una cola prioritaria es típicamente un montón, que puede ser un montón o un montón mínimo. Los valores deben ser del mismo tipo. Se almacenan en la cola en formato de montón (pedido parcial). Esperamos que hayas encontrado este artículo útil. Echa un vistazo a los otros artículos de Sugerencia de Linux para obtener consejos y tutoriales.