1. PriorityQueue data structure
The data structure of PriorityQueue (priority queue) in JDK7 is a binary heap. To be precise, it's a smallest pile.
A binary heap is a special heap, which is approximately a complete binary tree. The binary heap satisfies the characteristics: the key value of the parent node always maintains a fixed order relationship with the key value of any child node, and the left subtree and right subtree of each node are a binary heap.
The maximum heap is when the key value of the parent node is always greater than or equal to the key value of any child node. The minimum heap is when the key value of the parent node is always less than or equal to the key value of any child node.
The following figure is a maximum heap
priorityQueue team header is the smallest element in the given order.
priorityQueue does not allow null values and does not support non-comparable objects. priorityQueue requires the use of Comparable and Comparator interfaces to sort objects, and the elements in them will be processed according to priority when sorting.
The size of priorityQueue is unbounded, but the initial size can be specified when created. When adding queue elements, the queue will automatically expand.
priorityQueue is not thread-safe, similar PriorityBlockingQueue is thread-safe.
We know that queues follow the First-In-First-Out mode, but sometimes objects need to be processed based on priority in the queue. For example, we have an application that generates stock reports during daily trading hours, which requires processing a lot of data and takes a lot of processing time. When the client sends a request to this application, it actually enters the queue. We need to deal with priority customers first and then with ordinary users. In this case, Java's PriorityQueue (priority queue) will be very helpful.
PriorityQueue is an unbounded queue based on the priority heap. The elements in this priority queue can be sorted naturally by default or sorted when the queue is instantiated by the provided Comparator.
Priority queues do not allow null values and do not support non-comparable objects, such as user-defined classes. The priority queue requires the use of Java Comparable and Comparator interfaces to sort objects, and the elements in them will be processed according to priority when sorting.
The header of the priority queue is the smallest element based on natural sorting or Comparator sorting. If multiple objects have the same sort, it is possible to randomly take any of them. When we get the queue, we return the header object of the queue.
The size of the priority queue is unrestricted, but the initial size can be specified at creation time. When we add elements to the priority queue, the queue size will automatically increase.
PriorityQueue is non-thread-safe, so Java provides PriorityBlockingQueue (implementing the BlockingQueue interface) for Java multi-threaded environments.
2. PriorityQueue source code analysis
member:
priavte transient Object[] queue;private int size = 0;
1. The process of constructing a small top heap by PriorityQueue
Here we use the priorityQueue constructor to pass in a container as the parameter PriorityQueue(Collecntion<? extends E> example:
The process of constructing a small top heap is roughly divided into two steps:
Copy container data and check whether the container data is null
private void initElementsFromCollection(Collection<? extends E> c) { Object[] a = c.toArray(); // If c.toArray incorrectly doesn't return Object[], copy it. if (a.getClass() != Object[].class) a = Arrays.copyOf(a, a.length, Object[].class); int len = a.length; if (len == 1 || this.comparator != null) for (int i = 0; i < len; i++) if (a[i] == null) throw new NullPointerException(); this.queue = a; this.size = a.length;} Adjust to make the data satisfy the structure of the small top heap.
First, two adjustment methods: siftUp and siftDown
siftDown: When an initialization element is given, the element should be adjusted so that it meets the structural properties of the minimum heap. Therefore, the key value of element x is constantly compared and exchanged with the child from top to bottom until it is found that the key value of element x is less than or equal to the child's key value (that is, it is guaranteed to be smaller than its left and right node values), or it falls to the leaf node.
For example, as shown in the following diagram, adjust this node 9:
private void siftDownComparable(int k, E x) { Comparable<? super E> key = (Comparable<? super E>)x; int half = size >>> 1; // size/2 is the subscript of the first leaf node//As long as the leaf node is not reached while (k < half) { int child = (k << 1) + 1; //Left child Object c = queue[child]; int right = child + 1; //Find out the smallest and smallest children of the left and right children (right < size && ((Comparable<? super E>) c).compareTo((E) queue[right]) > 0) c = queue[child = right]; if (key.compareTo((E) c) <= 0) break; queue[k] = c; k = child; } queue[k] = key;} siftUp: priorityQueue inserts the new element into the tail each time a new element is added. Therefore, there should be the same adjustment process as siftDown, except to adjust from the bottom (leaf) upwards.
For example, fill in the node with key 3 in the following diagram:
private void siftUpComparable(int k, E x) { Comparable<? super E> key = (Comparable<? super E>) x; while (k > 0) { int parent = (k - 1) >>> 1; //Get parent subscript Object e = queue[parent]; if (key.compareTo((E) e) >= 0) break; queue[k] = e; k = parent; } queue[k] = key;}The overall process of building a small top heap is:
private void initFromCollection(Collection<? extends E> c) { initElementsFromCollection(c); heavy(); }Among them, heapify is the process of siftDown.
2. PriorityQueue capacity expansion process
As can be seen from the instance members, PriorityQueue maintains an Object[], so its expansion method is similar to the order table ArrayList.
Only the source code of the grow method is given here
private void grow(int minCapacity) { int oldCapacity = queue.length; // Double size if small; else grow by 50% int newCapacity = oldCapacity + ((oldCapacity < 64) ? (oldCapacity + 2) : (oldCapacity >> 1)); // overflow-conscious code if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); queue = Arrays.copyOf(queue, newCapacity); }It can be seen that when the Capacity of the array is not large, the capacity is not large every time. When the array capacity is greater than 64, double is expanded each time.
3. PriorityQueue application
eg1:
Here is the simplest application: find the K-th largest number from dynamic data.
The idea is to maintain a small top pile with size = k.
//data is dynamic data//heap maintains dynamic data//res is used to save the K-most value 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(); return true; } return false; } if(heap.peek() < data) { heap.poll(); heap.offer(data); } res[0] = heap.peek(); return true; }
eg2:
We have a user class Customer which does not provide any sort of sort. When we use it to create a priority queue, we should provide it with a comparator object.
Customer.java
package com.journaldev.collections; public class Customer { private int id; private String name; public Customer(int i, String n){ this.id=i; this.name=n; } public int getId() { return id; } public String getName() { return name; } } We use Java random numbers to generate random user objects. For natural sorting, we use Integer object, which is also an encapsulated Java object.
Here is the final test code showing how to use PriorityQueue:
PriorityQueueExample.java
package com.journaldev.collections; import java.util.Comparator;import java.util.PriorityQueue;import java.util.Queue;import java.util.Random; public class PriorityQueueExample { public static void main(String[] args) { //Priority queue natural sorting example Queue<Integer> integerPriorityQueue = new PriorityQueue<>(7); Random rand = new Random(); for(int i=0;i<7;i++){ integerPriorityQueue.add(new Integer(rand.nextInt(100))); } for(int i=0;i<7;i++){ Integer in = integerPriorityQueue.poll(); System.out.println("Processing Integer:"+in); } //Priority queue usage example Queue<Customer> customerPriorityQueue = new PriorityQueue<>(7, idComparator); addDataToQueue(customerPriorityQueue); pollDataFromQueue(customerPriorityQueue); } //Anonymous Comparator implements public static Comparator<Customer> idComparator = new Comparator<Customer>(){ @Override public int compare(Customer c1, Customer c2) { return (int) (c1.getId() - c2.getId()); } }; //Universal method used to add data to the queue private static void addDataToQueue(Queue<Customer> customerPriorityQueue) { Random rand = new Random(); for(int i=0; i<7; i++){ int id = rand.nextInt(100); customerPriorityQueue.add(new Customer(id, "Pankaj "+id)); } } // General method for fetching data from a queue private static void pollDataFromQueue(Queue<Customer> customerPriorityQueue) { while(true){ Customer cust = customerPriorityQueue.poll(); if(cust == null) break; System.out.println("Processing Customer with ID="+cust.getId()); } } } } Note that I use Java anonymous class that implements the Comparator interface and implements an id-based comparator.
When I run the above test program, I get the following output:
Processing Integer:9Processing Integer:16Processing Integer:18Processing Integer:25Processing Integer:33Processing Integer:75Processing Integer:77Processing Customer with ID=6Processing Customer with ID=20Processing Customer with ID=24Processing Customer with ID=28Processing Customer with ID=29Processing Customer with ID=82Processing Customer with ID=96
From the output results, it can be clearly seen that the smallest element is then taken out first at the head of the queue. If Comparator is not implemented, a ClassCastException will be thrown when creating a customerPriorityQueue.
Exception in thread "main" java.lang.ClassCastException: com.journaldev.collections.Customer cannot be cast to java.lang.Comparable at java.util.PriorityQueue.siftUpComparable(PriorityQueue.java:633) at java.util.PriorityQueue.siftUp(PriorityQueue.java:629) at java.util.PriorityQueue.offer(PriorityQueue.java:329) at java.util.PriorityQueue.add(PriorityQueue.java:306) at com.journaldev.collections.PriorityQueueExample.addDataToQueue(PriorityQueueExample.java:45) at com.journaldev.collections.PriorityQueueExample.main(PriorityQueueExample.java:25)