Usage and underlying implementation principle of PriorityQueue

Hello everyone , I meet you again , I'm your friend, Quan Jun .

Let's talk about use first , Let's talk about the principle

The queue follows the first in, first out （First-In-First-Out） Mode , But sometimes you need to process objects based on priority in the queue .

Two examples ：

1. Scheduler in operating system , When an assignment is finished , It is necessary to select a job with the highest priority among all the jobs waiting to be scheduled , You can also add a new job to the priority queue of the job .
2. In the application that generates stock reports during daily trading periods , Need to process a lot of data and spend a lot of processing time . When a customer sends a request to this application , It's actually in the queue . We need to deal with priority customers first and then ordinary users . under these circumstances ,Java Of PriorityQueue( Priority queue ) It will help .

PriorityQueue Class in Java1.5 Introduced and used as Java Collections Framework Part of .PriorityQueue It's an unbounded queue based on the priority heap , The elements in the priority queue can be sorted naturally by default or through the provided Comparator（ The comparator ） Sort when the queue is instantiated .

Priority queues do not allow null values , And it doesn't support non-comparable（ Cannot compare ） The object of , For example, user-defined classes . Priority queue request Java Comparable and Comparator Interface Sort objects , And when sorting, the elements will be processed according to the priority .

The head of the priority queue is based on natural sorting or Comparator The smallest element of sorting . If more than one object has the same sort , Then it is possible to take any one of them at random . When we get the queue , Returns the header object of the queue .

The size of the priority queue is unlimited , But you can specify the initial size at creation time . When we add elements to the priority queue , The queue size will automatically increase .

PriorityQueue It's not thread safe , therefore Java Provides PriorityBlockingQueue（ Realization BlockingQueue Interface ） be used for Java Multithreaded environment .

We have a user class Customer, It does not provide any sort . When we use it to establish a priority queue , It should be provided with a comparator object .

Customer.java

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21	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 number Generate random user objects . For natural sorting , We use Integer object , This is also a Sealed Java object .

Here is the final test code , Show how to use PriorityQueue：

PriorityQueueExample.java

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58

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) { // Example of natural sorting of priority queues 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 Realization public static Comparator<Customer> idComparator = new Comparator<Customer>(){ @Override public int compare(Customer c1, Customer c2) { return (int) (c1.getId() - c2.getId()); } }; // A general method for adding data to a 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)); } } // A 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 implemented it with Comparator Interface Java An anonymous class , And based on id Comparator .

When I run the above test program , I get the following output ：

1 2 3 4 5 6 7 8 9 10 11 12 13 14	Processing Integer:9 Processing Integer:16 Processing Integer:18 Processing Integer:25 Processing Integer:33 Processing Integer:75 Processing Integer:77 Processing Customer with ID=6 Processing Customer with ID=20 Processing Customer with ID=24 Processing Customer with ID=28 Processing Customer with ID=29 Processing Customer with ID=82 Processing Customer with ID=96

From the output results, we can clearly see , The smallest element is at the head of the queue and is therefore taken out first . If not implemented Comparator, In establishment customerPriorityQueue Thrown when ClassCastException.

1 2 3 4 5 6 7

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)

Realization principle ：

Java in PriorityQueue It's realized by a binary small top stack , It can be represented by a complete binary tree （ The weight of any non leaf node , Is not greater than the weight of its left and right child nodes ）, This means that you can use arrays as PriorityQueue The underlying implementation of .

In the figure above, we have numbered each element in the way of sequence traversal , If you are careful enough , You will find that the number of the parent node and the child node are related , More specifically, the number of parent-child nodes has the following relationship ：

leftNo = parentNo*2+1

rightNo = parentNo*2+2

parentNo = (nodeNo-1)/2

Through the above three formulas , It is easy to calculate the parent node and the subscript of the child node of a certain node . That's why you can use arrays directly to store heaps .

PriorityQueue Of peek() and element Operation is constant time ,add(), offer(), No parameters remove() as well as poll() The time complexity of the method is log(N).

Method analysis

add() and offer()

add(E e) and offer(E e) The meaning of is the same , All insert elements into the priority queue , It's just Queue The interface specifies that the two handle the insertion failure differently , The former throws an exception when the insert fails , Then it will return to false. about PriorityQueue There is no difference between the two methods .

The newly added elements may destroy the properties of the small top heap , So we need to make necessary adjustments .

//offer(E e)
public boolean offer(E e) {
    if (e == null)// It's not allowed to put null Elements 
        throw new NullPointerException();
    modCount++;
    int i = size;
    if (i >= queue.length)
        grow(i + 1);// Automatic expansion 
    size = i + 1;
    if (i == 0)// The queue was originally empty , This is the first element inserted 
        queue[0] = e;
    else
        siftUp(i, e);// adjustment 
    return true;
}

Copy

In the above code , Expansion function grow() Be similar to ArrayList Inside grow() function , Is to apply for a larger array , And copy the elements of the original array , No more details here . It should be noted that siftUp(int k, E x) Method , This method is used to insert elements x And maintain the characteristics of the heap .

//siftUp()
private void siftUp(int k, E x) {
    while (k > 0) {
        int parent = (k - 1) >>> 1;//parentNo = (nodeNo-1)/2
        Object e = queue[parent];
        if (comparator.compare(x, (E) e) >= 0)// Call comparer's comparison method 
            break;
        queue[k] = e;
        k = parent;
    }
    queue[k] = x;
}

Copy

New elements x It may destroy the nature of the small top pile , So it needs to be adjusted . The process of adjustment is ： from k The designated position starts , take x Layer by layer with the current point parent Compare and exchange , Until you meet x >= queue[parent] until . Note that the comparison here can be the natural order of elements , It can also rely on the sequence of comparators .

element() and peek()

element() and peek() The meaning of is exactly the same , All get but don't delete the team head element , That is, the element with the least weight in the queue , The only difference between the two is that the former throws an exception when the method fails , The latter returns null. According to the nature of the small top pile , The element at the top of the heap is the smallest one in the world ; Because the heap is represented by an array , According to the subscript relationship ,0 The element at the subscript is the heap top element . therefore Return the array directly 0 The element at the subscript .

The code is very concise ：

//peek()
public E peek() {
    if (size == 0)
        return null;
    return (E) queue[0];//0 The element at the subscript is the smallest 
}

Copy

remove() and poll()

remove() and poll() The semantics of methods are exactly the same , It's all about getting and deleting team leader elements , The difference is that when a method fails, it throws an exception , The latter returns null. Because deletion will change the structure of the queue , In order to maintain the properties of the small top reactor , Necessary adjustments are needed .

The code is as follows ：

public E poll() {
    if (size == 0)
        return null;
    int s = --size;
    modCount++;
    E result = (E) queue[0];//0 The element at the subscript is the smallest 
    E x = (E) queue[s];
    queue[s] = null;
    if (s != 0)
        siftDown(0, x);// adjustment 
    return result;
}

Copy

The above code first records 0 Element at subscript , And replace... With the last element 0 Elements of subscript location , Then call siftDown() Method to adjust the stack , Finally return to the original 0 The element in the subscript （ The smallest element ）. The key is siftDown(int k, E x) Method , The purpose of this method is from k The designated position starts , take x Layer by layer down with the smaller of the left and right children at the current point , until x Less than or equal to any one of the children .

//siftDown()
private void siftDown(int k, E x) {
    int half = size >>> 1;
    while (k < half) {
        // First find the smaller of the left and right children , It was recorded that c in , And use child Record its subscript 
        int child = (k << 1) + 1;//leftNo = parentNo*2+1
        Object c = queue[child];
        int right = child + 1;
        if (right < size &&
            comparator.compare((E) c, (E) queue[right]) > 0)
            c = queue[child = right];
        if (comparator.compare(x, (E) c) <= 0)
            break;
        queue[k] = c;// And then use c Replace the original value 
        k = child;
    }
    queue[k] = x;
}

Copy

remove(Object o)

remove(Object o) Method is used to delete the following in the queue o An equal element （ If there are more than one equal , Delete only one ）, The method is not Queue Methods in the interface , It is Collection Interface method . Because the deletion operation will change the queue structure , So make adjustments ; And because the position of the deleted element may be arbitrary , So the adjustment process is a little more cumbersome than other functions . say concretely ,remove(Object o) Can be divided into 2 In this case ：1. The last element is deleted . Just delete it , There is no need to adjust .2. It's not the last element to be deleted , Starting from the deletion point, call... Once with the last element as the reference siftDown() that will do . No more details here .

The specific code is as follows ：

//remove(Object o)
public boolean remove(Object o) {
    // Find the first satisfaction by traversing the array o.equals(queue[i]) Subscript of element 
    int i = indexOf(o);
    if (i == -1)
        return false;
    int s = --size;
    if (s == i) // situation 1
        queue[i] = null;
    else {
        E moved = (E) queue[s];
        queue[s] = null;
        siftDown(i, moved);// situation 2
        ......
    }
    return true;
}

Copy

reference ：

https://www.cnblogs.com/CarpenterLee/p/5488070.html

http://www.importnew.com/6932.html

Publisher ： Full stack programmer stack length , Reprint please indicate the source ：https://javaforall.cn/130832.html Link to the original text ：https://javaforall.cn