1. Estructura de datos de PriorityQueue
La estructura de datos de Priorityqueue (cola prioritaria) en JDK7 es un montón binario. Para ser precisos, es una pila más pequeña.
Un montón binario es un montón especial, que es aproximadamente un árbol binario completo. El montón binario satisface las características: el valor clave del nodo principal siempre mantiene una relación de orden fijo con el valor clave de cualquier nodo hijo, y el subárbol izquierdo y el subárbol derecho de cada nodo son un montón binario.
El montón máximo es cuando el valor clave del nodo principal es siempre mayor o igual al valor clave de cualquier nodo hijo. El montón mínimo es cuando el valor clave del nodo principal es siempre menor o igual al valor clave de cualquier nodo niño.
La siguiente figura es un montón máximo
El encabezado del equipo de priorityqueue es el elemento más pequeño en el orden dado.
Priorityqueue no permite valores nulos y no admite objetos no comparables. PriorityQueue requiere el uso de interfaces comparables y comparables para clasificar los objetos, y los elementos en ellos se procesarán de acuerdo con la prioridad al clasificar.
El tamaño de Priorityqueue está ilimitado, pero el tamaño inicial se puede especificar cuando se crea. Al agregar elementos de la cola, la cola se expandirá automáticamente.
PriorityQueue no es seguro de hilo, el bloqueo de prioridad similar es seguro de hilo.
Sabemos que las colas siguen el modo de primera salida, pero a veces los objetos deben procesarse en función de la prioridad en la cola. Por ejemplo, tenemos una aplicación que genera informes de acciones durante las horas diarias de negociación, lo que requiere procesar muchos datos y lleva mucho tiempo de procesamiento. Cuando el cliente envía una solicitud a esta aplicación, en realidad ingresa a la cola. Primero debemos lidiar con los clientes prioritarios y luego con los usuarios comunes. En este caso, la prioridad de Java (cola prioritaria) será muy útil.
Priorityqueue es una cola ilimitada basada en el montón de prioridad. Los elementos en esta cola prioritaria se pueden clasificar naturalmente de forma predeterminada o clasificarse cuando la cola es instanciada por el comparador proporcionado.
Las colas prioritarias no permiten valores nulos y no admiten objetos no comparables, como las clases definidas por el usuario. La cola prioritaria requiere el uso de interfaces comparables y comparables de Java para clasificar los objetos, y los elementos en ellos se procesarán de acuerdo con la prioridad al clasificar.
El encabezado de la cola de prioridad es el elemento más pequeño basado en la clasificación natural o la clasificación de comparación. Si múltiples objetos tienen el mismo tipo, es posible tomar al azar alguno de ellos. Cuando obtenemos la cola, devolvemos el objeto de encabezado de la cola.
El tamaño de la cola de prioridad no tiene restricciones, pero el tamaño inicial se puede especificar en el momento de la creación. Cuando agregamos elementos a la cola de prioridad, el tamaño de la cola aumentará automáticamente.
PriorityQueue no es seguro de huella, por lo que Java proporciona priorityblockingqueue (implementando la interfaz BloquingQueue) para entornos de múltiples subprocesos Java.
2. Análisis del código fuente de priorityqueue
miembro:
Priavte objeto transitorio [] cola; private int size = 0;
1. El proceso de construir un montón superior pequeño por priorityqueue
Aquí usamos el constructor de priorityqueue para pasar en un contenedor como parámetro priorityqueue (Collecntion <? Extiende e> ejemplo:
El proceso de construcción de un montón superior pequeño se divide aproximadamente en dos pasos:
Copie los datos del contenedor y verifique si los datos del contenedor son nulos
privado void initelementsFromCollection (colección <? extiende e> c) {objeto [] a = c.toarray (); // Si C.ToArray incorrectamente no devuelve objeto [], cópielo. if (a.getClass ()! = Object []. class) a = arrays.copyOf (a, a.length, object []. class); int len = A.Length; if (len == 1 || this.comparator! = null) para (int i = 0; i <len; i ++) if (a [i] == null) tirar nueva nullPointerException (); this.Queue = a; this.size = a.length;} Ajuste para que los datos satisfagan la estructura del pequeño montón superior.
Primero, dos métodos de ajuste: Siftup y Siftdown
Downdown: cuando se da un elemento de inicialización, el elemento debe ajustarse para que cumpla con las propiedades estructurales del montón mínimo. Por lo tanto, el valor clave del elemento X se compara e intercambia constantemente con el niño de arriba a abajo hasta que se encuentra que el valor clave del elemento x es menor o igual al valor clave del niño (es decir, se garantiza que es más pequeño que sus valores de nodo izquierdo y derecho), o cae al nodo de hoja.
Por ejemplo, como se muestra en el siguiente diagrama, ajuste este nodo 9:
Private void siftdownComparable (int k, e x) {comparable <? super e> key = (comparable <? Super E>) x; int Half = size >>> 1; // tamaño/2 es el subíndice del primer nodo de hoja // siempre que el nodo de la hoja no se alcance mientras (k <mitad) {int child = (k << 1) + 1; // objeto infantil izquierdo C = cola [niño]; int correcto = niño + 1; // Descubre los niños más pequeños y más pequeños de los niños izquierdo y derecho (derecha <size && ((comparable <? Super E>) c) .compareto ((e) cola [derecha])> 0) c = queue [child = right]; if (key.compareto ((e) c) <= 0) ruptura; cola [k] = c; k = niño; } queue [k] = key;} Siftup: Priorityqueue inserta el nuevo elemento en la cola cada vez que se agrega un nuevo elemento. Por lo tanto, debe haber el mismo proceso de ajuste que Siftdown, excepto para ajustarse desde la parte inferior (hoja) hacia arriba.
Por ejemplo, complete el nodo con la clave 3 en el siguiente diagrama:
Private void siftupComparable (int k, e x) {comparable <? super e> key = (comparable <? Super E>) x; while (k> 0) {int parent = (k - 1) >>> 1; // Obtener objeto de subíndice principal e = cola [parent]; if (key.compareto ((e) e)> = 0) ruptura; cola [k] = e; k = padre; } queue [k] = key;}El proceso general de construcción de un montón superior es:
Private void initFromCollection (colección <? extiende e> c) {initElementsFromCollection (c); pesado(); }Entre ellos, Heapify es el proceso de Siftdown.
2. Proceso de expansión de la capacidad priorityqueue
Como se puede ver en los miembros de la instancia, PriorityQueue mantiene un objeto [], por lo que su método de expansión es similar al ArrayList de la tabla de pedidos.
Solo se da el código fuente del método de crecimiento aquí
Private void Grow (int mincapacity) {int OldCapacity = queue.length; // tamaño doble si es pequeño; de lo contrario crece en un 50% int newCapacity = OldCapacity + ((OldCapacity <64)? (OldCapacity + 2): (OldCapacity >> 1)); // Código consciente de desbordamiento if (newCapacity - max_array_size> 0) newCapacity = HugeCapacity (minCapacity); cola = arrays.copyOf (cola, newcapacity); }Se puede ver que cuando la capacidad de la matriz no es grande, la capacidad no es grande cada vez. Cuando la capacidad de matriz es mayor que 64, el doble se expande cada vez.
3. Aplicación de PriorityQueue
Eg1:
Aquí está la aplicación más simple: encuentre el número más grande de K-Th de Dynamic Data.
La idea es mantener una pequeña pila superior con tamaño = k.
// Los datos son datos dinámicos // Heap mantiene datos dinámicos // Res se usa para guardar el valor K-Most public boolean kthLargest (int data, int k, priorityqueue <integer> heap, int [] res) {if (heap.size () <k) {heap.offer (data); if (heap.size () == k) {res [0] = Heap.peek (); devolver verdadero; } return false; } if (Heap.Peek () <data) {Heap.Poll (); Heap.offer (datos); } res [0] = Heap.Peek (); devolver verdadero; }
EG2:
Tenemos un cliente de clase de usuario que no proporciona ningún tipo de tipo. Cuando lo usamos para crear una cola prioritaria, debemos proporcionarle un objeto comparador.
Cliente.java
paquete com.journaldev.collections; Cliente de clase pública {private int id; nombre de cadena privada; Public Customer (int i, String n) {this.id = i; this.name = n; } public int getId () {return id; } public String getName () {nombre de retorno; }} Usamos números aleatorios Java para generar objetos de usuario aleatorios. Para la clasificación natural, usamos objeto entero, que también es un objeto Java encapsulado.
Aquí está el código de prueba final que muestra cómo usar priorityqueue:
PriorityqueueeExample.java
paquete com.journaldev.collections; import java.util.comparator; import java.util.priorityqueue; import java.util.queue; import java.util.random; clase pública priorityqueueeExample {public static void main (string [] args) {// prioridad cola ejemplo de clasificación natural cola <integer> integerpriorityqueue = new priorityqueue <> (7); Rand aleatorio = new Random (); for (int i = 0; i <7; i ++) {integerpriorityqueue.add (nuevo entero (rand.nextint (100))); } para (int i = 0; i <7; i ++) {Integer in = IntegerPriorityqueue.Poll (); System.out.println ("Processing Integer:"+in); } // Priority Queue Uso Ejemplo de cola <Customer> CustomerPriorityqueue = New Priorityqueue <> (7, IDComparator); Adddatatoqueue (CustomerPriorityqueue); polldataFromqueue (CustomerPriorityqueue); } // Comparador anónimo implementa Public Static Comparator <Customer> IDComparator = New Comparator <Customer> () {@Override public int Compare (Customer C1, Customer C2) {return (int) (c1.getID () - c2.getID ()); }}; // Método universal utilizado para agregar datos a la cola void static private adddatatoqueue (cola <Customer> CustomerPriorityqueue) {Random Rand = new Random (); for (int i = 0; i <7; i ++) {int id = rand.nextint (100); CustomerPriorityqueue.Add (nuevo cliente (ID, "Pankaj"+id)); }} // Método general para obtener datos de una cola void estática privada polldataFromqueue (queue <Customer> CustomerPriorityqueue) {while (true) {Customer cust = customerPriorityqueue.poll (); if (cust == null) ruptura; System.out.println ("Processing Cliente con id ="+cust.getID ()); }}}} Tenga en cuenta que uso la clase Anónima Java que implementa la interfaz del comparador e implementa un comparador basado en ID.
Cuando ejecuto el programa de prueba anterior, obtengo la siguiente salida:
Integer de procesamiento: 9 de proceso entero: 16 procesamiento número entero: 18 procesamiento entero: 25 procesamiento entero: 33procesamiento entero: 75 procesamiento entero: 77 procesar cliente con id = 6 customer con identificación con identificación de Id = 20 ID = 82 Procedimiento del cliente con ID = 96
A partir de los resultados de la salida, se puede ver claramente que el elemento más pequeño se saca primero en la cabeza de la cola. Si no se implementa un comparador, se lanzará una ClassCastException al crear un CustomerPriorityQueue.
Excepción en el hilo "Main" java.lang.classcastException: com.journaldev.collections.customer no se puede lanzar a java.lang.comparable en java.util.priorityqueue.siftupcomparable (priorityqueue.java:633) java.util.priorityqueue.offer (priorityqueue.java:329) en java.util.priorityqueue.add (priorityqueue.java:306) en com.journaldev.collections.priorityqueueexample.adddatatatoue com.journaldev.collections.priorityqueueeExample.main (priorityqueueeExample.java:25)