preface
A Queue is a data structure with a first in, first out (FIFO) feature, and PriorityQueue is a subclass of it. Unlike a first in, first out (FIFO), PriorityQueue can control the output order (priority) of elements through a comparator. This article will take a look at the source code for PriorityQueuede and see how it is implemented.
Class inheritance relation
Let’s start with the Queue interface:
public interface Queue<E> extends Collection<E>
Copy the codeThe Queue interface inherits the Collection interface, which represents a Collection. It provides three methods: add, delete, and get, each with two implementations.
// Add elements
boolean add(E e);
boolean offer(E e);
// Delete elements
E remove(a);
E poll(a);
// Get the element
E element(a);
E peek(a);
Copy the codeThe difference between the two implementations is that Add, Remove, and Element all throw one more exception than the corresponding Offer, poll, and peek. For the Add method, IllegalStateException is thrown if there is not enough capacity to add a new element, and offer returns false. For the remove method, NoSuchElementException is thrown if the queue is empty, and the poll method returns NULL. For the Element method, NoSuchElementException is thrown if the queue is empty, and the PEEK method returns NULL.
Now look at the PriorityQueue class:
public class PriorityQueue<E> extends AbstractQueue<E>
implements java.io.Serializable
Copy the codeWell, instead of implementing Queue directly, we’re going to inherit AbstractQueue. Again, AbstractQueue should also be a template abstract class (similar to AbstractMap and AbstractList). To see AbstractQueue:
public abstract class AbstractQueue<E>
extends AbstractCollection<E>
implements Queue<E>
Copy the codeSure enough, AbstractCollection class is inherited and Queue interface is implemented. If it’s a template class there must be template methods. The AbstractQueue source code only implements the add, remove, and elemet methods.
public boolean add(E e) {
if (offer(e)) / / call the offer. }public E remove(a) {
E x = poll(); / / call the poll. }public E element(a) {
E x = peek(); / / peek. }Copy the codeAs you can see, they call Offer, poll, and peek, respectively. That is, if you want to implement a queue with AbstractQueue, you must implement the Offer, poll, and PEEK methods. The following is a tight analysis of PriorityQueue source code.
PriorityQueue source code analysis
Looking at the source code, PriorityQueue is implemented using a “maximum priority heap”, where the top element of the heap is the element with the highest priority. Kind of integrated big root heap and small root heap function.
Important attributes
By the nature of the heap, the storage structure must be an array; Since different priorities are supported, there must be a comparator, that is, support for custom sorting and sequential sorting.
// The default capacity is 11
private static final int DEFAULT_INITIAL_CAPACITY = 11;
// The storage structure of the heap, storing elements
transient Object[] queue; // Not serializable
// The number of elements currently stored
int size;
// Set priority
private final Comparator<? super E> comparator;
// Avoid OOM, the maximum size of the array can be allocated
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
Copy the codeThe constructor
There are many constructors for PriorityQueue. The main arguments are capacity and comparator:
public PriorityQueue(a) {
this(DEFAULT_INITIAL_CAPACITY, null); // Default natural order
}
public PriorityQueue(int initialCapacity) {
this(initialCapacity, null); // Customize the initial capacity
}
public PriorityQueue(Comparator<? super E> comparator) {
this(DEFAULT_INITIAL_CAPACITY, comparator); // Custom comparator
}
public PriorityQueue(int initialCapacity,
Comparator<? super E> comparator) {...// Assign the corresponding value
}
public PriorityQueue(Collection<? extends E> c) {
// roll c into a heap
if (c instanceof SortedSet<?>) {
... // SortedSet comes with a comparator
}
else if (c instanceof PriorityQueue<?>) {
... // PriorityQueue has its own comparator
}
else{... }}public PriorityQueue(PriorityQueue<? extends E> c) {...// Get the comparator from PriorityQueue and roll c into a heap
}
public PriorityQueue(SortedSet<? extends E> c) {...// Get the comparator from SortedSet and roll c into a heap
}
Copy the codeReuse method
PriorityQueue supports capacity expansion.
// minCapacity Indicates the minimum capacity required
private void grow(int minCapacity) {
int oldCapacity = queue.length; // Get the current capacity
// Double size if small; else grow by 50%
If the old capacity is less than 64, increase the old capacity by +2
If the old capacity is greater than or equal to 64, increase the size of the old capacity by half
int newCapacity = oldCapacity + ((oldCapacity < 64)? (oldCapacity +2) :
(oldCapacity >> 1));
// overflow-conscious code
if (newCapacity - MAX_ARRAY_SIZE > 0) // This handles large volumes
newCapacity = hugeCapacity(minCapacity);
queue = Arrays.copyOf(queue, newCapacity); // Copy stored data
}
Copy the codeThe size of each expansion is still quite large, either doubling the original size or increasing by half.
Before we look at how to add, delete, and get elements, here are a few things to know:
- The subscript of the last non-leaf node of a complete binary tree is (n-2) / 2;
- In a complete binary tree, if the subscript of a non-leaf node is I, its parent is subscript (i-1) /2, its left child is subscript 2 * I + 1, and its right child is subscript 2 * I + 2.
Offer method
public boolean offer(E e) {
if (e == null)
throw new NullPointerException();
modCount++;
int i = size;
if (i >= queue.length)
grow(i + 1); // If the current capacity is exceeded, expand the capacity
siftUp(i, e); // New elements are added to the end of the array and then moved up to build the heap
size = i + 1; // The current size is increased by 1
return true;
}
Copy the codeThe siftUp method will eventually call either a siftUpUsingComparator or a siftUpComparable method, which are similar implementations, so let’s look directly at the siftUpUsingComparator method.
// To move up is to constantly compare with the parent
private static <T> void siftUpUsingComparator(
int k, T x, Object[] es, Comparator<? super T> cmp) {
while (k > 0) {
int parent = (k - 1) > > >1; // parent subscript
Object e = es[parent];
if (cmp.compare(x, (T) e) >= 0) // If the priority is higher, the comparison continues
break;
es[k] = e;
k = parent;
}
es[k] = x;
}
Copy the codeEvery time you add an element, keep the heap sorted.
Poll method
public E poll(a) {
final Object[] es;
final E result;
// Return the top of the heap element
if ((result = (E) ((es = queue)[0))! =null) {
modCount++;
final int n;
final E x = (E) es[(n = --size)]; // Change the tail element to the first one
es[n] = null;
if (n > 0) {
final Comparator<? super E> cmp;
if ((cmp = comparator) == null) // Move down to adjust the natural sequence
siftDownComparable(0, x, es, n);
else // Custom order down adjustment
siftDownUsingComparator(0, x, es, n, cmp); }}return result;
}
Copy the codeThe poll method returns the first element (the top of the heap) and deletes the element from the heap. The deletion process is to replace the first element with the last, and then move it down. Here’s a direct look at the siftDownUsingComparator method:
private static <T> void siftDownUsingComparator(
int k, T x, Object[] es, int n, Comparator<? super T> cmp) {
// assert n > 0;
int half = n >>> 1; // Subscript the last non-leaf node (since size has been reduced by 1)
while (k < half) {
int child = (k << 1) + 1; / / the left child
Object c = es[child];
int right = child + 1; / / right child
if (right < n && cmp.compare((T) c, (T) es[right]) > 0)
c = es[child = right]; // Choose the one with the highest priority from the left and right children
if (cmp.compare(x, (T) c) <= 0)
break;
es[k] = c; // Move the target element down
k = child;
}
es[k] = x;
}
Copy the codeHeap adjustments are made every time the head of the queue element is popped up.
The remove method
The poll method can be seen as a special case of the remove method, which permanently removes the first element.
public boolean remove(Object o) {
int i = indexOf(o); // Locate the element to be deleted
if (i == -1)
return false;
else {
removeAt(i); // Remove the element at the specified location
return true; }}Copy the codeThe removeAt method is called:
E removeAt(int i) {
// assert i >= 0 && i < size;
final Object[] es = queue;
modCount++;
int s = --size; // size has been reduced by 1
if (s == i) // removed last element
es[i] = null; // The last element has been deleted
else {
E moved = (E) es[s]; / / stern element
es[s] = null;
siftDown(i, moved); // Specify the element to replace the trailing element, and then adjust
if (es[i] == moved) {
siftUp(i, moved); // Move up if the specified position is changed to a trailing element (no move down occurs)
if(es[i] ! = moved)returnmoved; }}return null; // Return null for normal deletion
}
Copy the codeconclusion
- PriorityQueue is implemented based on the maximum priority heap, which can be a large or small root heap depending on the comparator;
- PriorityQueue does not support NULL;
- PriorityQueue is not thread-safe and can be used in multithreaded environments
java.util.concurrent.PriorityBlockingQueue; - use
iterator()Traversal, does not guarantee that the output sequence is ordered, in fact, traversal is the storage array.
Pay attention to wechat public number, the latest technology dry goods real-time push
