Java PriorityQueue use

The Queue and PriorityQueue

We know that a Queue is a first-in, first-out Queue.

Do business in bank counter, we assume only a counter is dealing with business, but the person that deals with business is very much, how to do?

Each person can take a number first, for example, A1, A2, A3… And then we’re going to do it in order of numbers, which is essentially a Queue.

If a VIP customer arrives at this moment, his number is V1, although the current queue is A10, A11, A12… But the customer number under the counter was V1.

At this point, we found that to implement the “VIP queue-jumping” business, the Queue can not use the Queue, because the Queue will strictly FIFO the first element. What we need is a PriorityQueue: PriorityQueue.

PriorityQueue differs from Queue in that the order in which it is queued depends on the priority of the elements. A call to remove() or poll() on PriorityQueue always returns the element with the highest priority.

PriorityQueue instance

1. Customize the Comparator

The Comparable interface must be implemented for the elements placed in PriorityQueue, which determines the queue’s priority based on the order in which the elements are sorted.

What if the element we’re putting in doesn’t implement the Comparable interface?

PriorityQueue allows us to provide a Comparator object to determine the order of two elements. Let’s take the bank queuing business as an example to implement a PriorityQueue:

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

public class Main {
    public static void main(String[] args) {
        Queue<User> q = new PriorityQueue<>(new UserComparator());
        // Add three elements to the queue:
        q.offer(new User("Bob"."A1"));
        q.offer(new User("Alice"."A2"));
        q.offer(new User("Boss"."V1"));
        System.out.println(q.poll()); // Boss/V1
        System.out.println(q.poll()); // Bob/A1
        System.out.println(q.poll()); // Alice/A2
        System.out.println(q.poll()); // null because the queue is empty}}class UserComparator implements Comparator<User> {
    public int compare(User u1, User u2) {
        if (u1.number.charAt(0) == u2.number.charAt(0)) {
            // If two people start with A or V, compare the size of the numbers:
            return u1.number.compareTo(u2.number);
        }
        if (u1.number.charAt(0) = ='V') {
            // The number of U1 starts with V and has a high priority:
            return -1;
        } else {
            return 1; }}}class User {
    public final String name;
    public final String number;

    public User(String name, String number) {
        this.name = name;
        this.number = number;
    }

    public String toString(a) {
        return name + "/"+ number; }}Copy the code

The key to implementing PriorityQueue is the provided UserComparator object, which is responsible for comparing the sizes of two elements (the smaller comes first). The UserComparator always returns numbers starting with V first and only compares numbers if they start with the same number.

The UserComparator comparison logic above is actually wrong. It puts A10 before A2. Please try to fix this.

2. Use PriorityQueue to implement the big top heap

PriorityQueue is a small top heap by default, but a large top heap can be implemented by passing in a custom Comparator function. The following code implements a large top heap with an initial size of 11. We simply pass in a custom Comparator function to implement the big top heap.


private static final int DEFAULT_INITIAL_CAPACITY = 11;
PriorityQueue<Integer> maxHeap=new PriorityQueue<Integer>(DEFAULT_INITIAL_CAPACITY, new Comparator<Integer>() {
        @Override
        public int compare(Integer o1, Integer o2) {                
            returno2-o1; }});Copy the code

PriorityQueue principle

PriorityQueue in Java is implemented through the binary small top heap.

PriorityQueue implements the Queue interface and does not allow null elements.

Note that null elements cannot be put in! Note that null elements cannot be put in! Note that null elements cannot be put in!

It is implemented via a heap, specifically a small top heap via a complete binary tree (the weight of any non-leaf node is no greater than the weight of its left and right children), which means that an array can be used as the underlying implementation of PriorityQueue.

Analysis of common methods

Peek () and Element operations for PriorityQueue are constant time, while add(), Offer (), remove() without arguments, and poll() all have log(N) time complexity.

1. Add and offer

Add (E E) and Offer (E E) have the same semantics, they both insert elements to the priority Queue, but the Queue interface specifies that they are different when the insert fails. The former raises an exception when the insert fails, and the latter returns false. There’s really no difference between these two methods for PriorityQueue.

The addition of new elements may destroy the nature of the small top heap, so necessary adjustments are required.

Element and Peek

Element () and peek() are semantically identical in that they both get but do not remove the first element of the queue, the element with the least weight in the queue. The only difference is that the former throws an exception when the method fails, while the latter returns NULL.

According to the properties of the small top heap, the element at the top of the heap is the smallest globally; Since the heap is represented as an array, the element at subscript 0 is both the top element of the heap according to the subscript relationship. So just return the element at the index of array 0.

3. remove and poll

The semantics of the remove() and poll() methods are identical, fetching and deleting the first element of the queue, except that the former throws an exception when the method fails, while the latter returns NULL.

Because deletion changes the structure of the queue, necessary adjustments are required to maintain the nature of the small top heap.

4, the remove (Object o)

The remove(Object O) method is used to remove an element in a Queue that is equal to o (if there are multiple equal elements, only one is removed). This method is not a method in the Queue interface, but a method in the Collection interface.

Because deleting changes the queue structure, it is adjusted; And because the location of the deleted element can be arbitrary, the adjustment process is a bit more tedious than other functions.

Specifically, remove(Object O) can be divided into two cases: 1. The last element is deleted. Delete directly, do not need to adjust. 2. Instead of deleting the last element, call siftDown() once from the deletion point, referencing the last element. I will not repeat it here.

summary

PriorityQueue implements a PriorityQueue: when an element is fetched from the head of the queue, the element with the highest priority is always fetched.

PriorityQueue is sorted by default by the order in which elements are compared (the Comparable interface must be implemented), or you can customize the sorting algorithm using the Comparator (elements do not have to implement the Comparable interface).

Reference:

www.cnblogs.com/CarpenterLe…

Blog.csdn.net/weixin_3036…