In the case of Stack and Queue, a Java ArrayDeque, there is a special Queue called PriorityQueue. The function of priority queues is to ensure that each fetched element has the lowest weight in the queue (Java priority queues take the smallest element, C++ priority queues take the largest element). This is where size comes in. The size of an element can be determined by the natural ordering of the elements, or by a Comparator passed in during construction.

Java PriorityQueue implements the Queue interface and does not allow null elements. 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.

In the figure above, we have numbered each element in the way of sequential traversal. If you are careful enough, you will find that there is a correlation between the number of the parent node and that of the child node. Specifically, there is a relationship between the number of the parent node and that of the child node:

leftNo = parentNo*2+1

rightNo = parentNo*2+2

parentNo = (nodeNo-1)/2

With the above three formulas, it is easy to calculate the subscripts of the parent and child nodes of a node. This is why you can store the heap directly in arrays.

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

Add (E E) and Offer (E E) have the same semantics. They both insert elements into the priority Queue, but the Queue interface specifies that they are handled differently 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.

//offer(E e)
public boolean offer(E e) {
    if (e == null)// Null elements are not allowed
        throw new NullPointerException();
    modCount++;
    int i = size;
    if (i >= queue.length)
        grow(i + 1);// Automatic capacity expansion
    size = i + 1;
    if (i == 0)// The queue was empty, which was the first element to be inserted
        queue[0] = e;
    else
        siftUp(i, e);/ / adjust
    return true;
}
Copy the code

In the code above, the grow() function is similar to the grow() function in the ArrayList. It obtains a larger array and copies the elements of the original array, which is not described here. Note the siftUp(int k, E x) method, which is used to insert element 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 the comparison method of the comparator
            break;
        queue[k] = e;
        k = parent;
    }
    queue[k] = x;
}
Copy the code

The addition of element X may break the nature of the small top heap, so it needs to be adjusted. The adjustment process is as follows: from the position specified by k, x is compared and swapped layer by layer with the parent of the current point until x >= queue[parent] is satisfied. Note that the comparison can be either a natural order of elements or a comparator order.

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.

The code is as follows:

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

This code first records the element at 0 subscript, replaces the element at 0 subscript with the last one, adjusts the heap by calling siftDown(), and finally returns the original element at 0 subscript (the smallest element). The focus is on the siftDown(int k, E x) method, which starts at the position specified by K and swaps x layer by layer with the smaller of the left and right children of the current point until x is less than or equal to either of the left and right children.

//siftDown()
private void siftDown(int k, E x) {
    int half = size >>> 1;
    while (k < half) {
    	// First find the younger of the left and right children, record it in c, and record its subscript with child
        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;// Then replace the original value with c
        k = child;
    }
    queue[k] = x;
}
Copy the code