Abstract:
In Java, PriorityQueue is implemented by a binary small top heap and can be represented by a complete binary tree. Starting from the Queue interface function, combined with vivid diagrams, this paper analyzes the specific process and time complexity of each operation of PriorityQueue in a simple way, which will enable readers to establish a clear and in-depth understanding of PriorityQueue. 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.
General introduction
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.
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.
API
1. Internal attributes
Private static Final Int DEFAULT_INITIAL_CAPACITY = 11; private static final Int DEFAULT_INITIAL_CAPACITY = 11; // Array transient Object[] queue; Private int size = 0; private int size = 0; // Private final Comparator Comparator; // Transient int modCount = 0;Copy the codeAs we know, there are two main types of heap data structure: large root heap and small root heap. And every time we adjust the structure, we’re constantly comparing the values of two elements according to some rule, and then adjusting the structure, and that’s where we need our comparator. So building a PriorityQueue instance is all about initializing the array capacity and the comparator. PriorityQueue has the following constructors:
2. Constructor
/** * Creates a {@code PriorityQueue} with the default initial * capacity (11) that orders its elements according to their * {@linkplain Comparable natural ordering}. */ public PriorityQueue() { this(DEFAULT_INITIAL_CAPACITY, null); } /** * Creates a {@code PriorityQueue} with the specified initial * capacity that orders its elements according to their * {@linkplain Comparable natural ordering}. * * @param initialCapacity the initial capacity for this priority queue * @throws IllegalArgumentException if {@code initialCapacity} is less * than 1 */ public PriorityQueue(int initialCapacity) { this(initialCapacity, null); } /** * Creates a {@code PriorityQueue} with the default initial capacity and * whose elements are ordered according to the specified comparator. * * @param comparator the comparator that will be used to order this * priority queue. If {@code null}, The {@linkplain Comparable * natural order} of the elements will be used. * @since 1.8 */ public PriorityQueue(Comparator comparator) { this(DEFAULT_INITIAL_CAPACITY, comparator); } /** * Creates a {@code PriorityQueue} with the specified initial capacity * that orders its elements according to the specified comparator. * * @param initialCapacity the initial capacity for this priority queue * @param comparator the comparator that will be used to order this * priority queue. If {@code null}, the {@linkplain Comparable * natural ordering} of the elements will be used. * @throws IllegalArgumentException if {@code initialCapacity} is * less than 1 */ public PriorityQueue(int initialCapacity, Comparator comparator) { // Note: This restriction of at least one is not actually needed, // But continues for 1.5 compatibility if (initialCapacity < 1) throw new IllegalArgumentException(); // But continues for 1.5 compatibility if (initialCapacity < 1) throw new IllegalArgumentException(); this.queue = new Object[initialCapacity]; this.comparator = comparator; } /** * Creates a {@code PriorityQueue} containing the elements in the * specified collection. If the specified collection is an instance of * a {@link SortedSet} or is another {@code PriorityQueue}, this * priority queue will be ordered according to the same ordering. * Otherwise, this priority queue will be ordered according to the * {@linkplain Comparable natural ordering} of its elements. * * @param c the collection whose elements are to be placed * into this priority queue * @throws ClassCastException if elements of the specified collection * cannot be compared to one another according to the priority * queue's ordering * @throws NullPointerException if the specified collection or any * of its elements are null */ @SuppressWarnings("unchecked") public PriorityQueue(Collection c) { if (c instanceof SortedSet) { SortedSet ss = (SortedSet) c; this.comparator = (Comparator) ss.comparator(); initElementsFromCollection(ss); } else if (c instanceof PriorityQueue) { PriorityQueue pq = (PriorityQueue) c; this.comparator = (Comparator) pq.comparator(); initFromPriorityQueue(pq); } else { this.comparator = null; initFromCollection(c); } } /** * Creates a {@code PriorityQueue} containing the elements in the * specified priority queue. This priority queue will be * ordered according to the same ordering as the given priority * queue. * * @param c the priority queue whose elements are to be placed * into this priority queue * @throws ClassCastException if elements of {@code c} cannot be * compared to one another according to {@code c}'s * ordering * @throws NullPointerException if the specified priority queue or any * of its elements are null */ @SuppressWarnings("unchecked") public PriorityQueue(PriorityQueue c) { this.comparator = (Comparator) c.comparator(); initFromPriorityQueue(c); } /** * Creates a {@code PriorityQueue} containing the elements in the * specified sorted set. This priority queue will be ordered * according to the same ordering as the given sorted set. * * @param c the sorted set whose elements are to be placed * into this priority queue * @throws ClassCastException if elements of the specified sorted * set cannot be compared to one another according to the * sorted set's ordering * @throws NullPointerException if the specified sorted set or any * of its elements are null */ @SuppressWarnings("unchecked") public PriorityQueue(SortedSet c) { this.comparator = (Comparator) c.comparator(); initElementsFromCollection(c); }Copy the codeThere are the first four types of constructors, with the first three internally calling the last constructor. Two arguments, one to specify the size of the array to initialize and one to initialize a comparator. If they are not explicitly specified, DEFAULT_INITIAL_CAPACITY (11) is default for capacity and null is comparator. Let’s take a look at how you can add and remove nodes to a PriorityQueue instance while keeping the original heap structure intact.
3. Common functions
Methods analyze the
Boolean add(E E) and Boolean offer(E E)
/** * Inserts the specified element into this priority queue. * * @return {@code true} (as specified by {@link Collection#add}) * @throws ClassCastException if the specified element cannot be * compared with elements currently in this priority queue * according to the priority queue's ordering * @throws NullPointerException if the specified element is null */ public boolean add(E e) { return offer(e); } /** * Inserts the specified element into this priority queue. * * @return {@code true} (as specified by {@link Queue#offer}) * @throws ClassCastException if the specified element cannot be * compared with elements currently in this priority queue * according to the priority queue's ordering * @throws NullPointerException if the specified element is null */ public boolean offer(E e) { if (e == null) throw new NullPointerException(); modCount++; int i = size; if (i >= queue.length) grow(i + 1); size = i + 1; if (i == 0) queue[0] = e; else siftUp(i, e); return true; }Copy the codeThe add method actually calls the Offer method internally, so let’s look at how offer implements adding an element to the heap structure without breaking it. First of all, this method defines a variable gain actual storage element in the queue number, followed by an if judgment, if the array has been fully used (there is no available space), will call grow method expansion, turns method can judge according to the concrete situation, if the original array will expand twice larger + 2, otherwise a 50% increase in capacity, Because the specific code is relatively clear, it is not repeated here.
/**
* Increases the capacity of the array.
*
* @param minCapacity the desired minimum capacity
*/
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);
}
Copy the codeThen determine whether the complete binary tree is empty. If there are no nodes, the new node can be used as the root node. Otherwise, siftUp will be called to add new elements and adjust the structure, so this method is important.
/** * Inserts item x at position k, maintaining heap invariant by * promoting x up the tree until it is greater than or equal to * its parent, or is the root. * * To simplify and speed up coercions and comparisons. the * Comparable and Comparator versions are separated into different * methods that are otherwise identical. (Similarly for siftDown.) * * @param k the position to fill * @param x the item to insert */ private void siftUp(int k, E x) { if (comparator ! = null) siftUpUsingComparator(k, x); else siftUpComparable(k, x); }Copy the code/** * Retrieves, but does not remove, the head of this queue. This method * differs from {@link #peek peek} only in that it throws an exception if * this queue is empty. * * This implementation returns the result of peek * unless the queue is empty. * * @return the head of this queue * @throws NoSuchElementException if this queue is empty */ public E element() { E x = peek(); if (x ! = null) return x; else throw new NoSuchElementException(); }Copy the code
@SuppressWarnings("unchecked")
public E peek() {
return (size == 0) ? null : (E) queue[0];
}
Copy the code
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.
/** * Retrieves and removes the head of this queue. This method differs * from {@link #poll poll} only in that it throws an exception if this * queue is empty. * * This implementation returns the result of poll * unless the queue is empty. * * @return the head of this queue * @throws NoSuchElementException if this queue is empty */ public E remove() { E x = poll(); if (x ! = null) return x; else throw new NoSuchElementException(); }Copy the code
/**
* Retrieves and removes the head of the queue represented by this deque
* (in other words, the first element of this deque), or returns
* {@code null} if this deque is empty.
*
*
This method is equivalent to {@link #pollFirst}.
*
* @return the head of the queue represented by this deque, or
* {@code null} if this deque is empty
*/
public E poll() {
return pollFirst();
}
Copy the code
public E pollFirst() {
int h = head;
@SuppressWarnings("unchecked")
E result = (E) elements[h];
// Element is null if deque empty
if (result == null)
return null;
elements[h] = null; // Must null out slot
head = (h + 1) & (elements.length - 1);
return result;
}
Copy the code
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. Delete not the last element.
/**
* Removes a single instance of the specified element from this queue,
* if it is present. More formally, removes an element {@code e} such
* that {@code o.equals(e)}, if this queue contains one or more such
* elements. Returns {@code true} if and only if this queue contained
* the specified element (or equivalently, if this queue changed as a
* result of the call).
*
* @param o element to be removed from this queue, if present
* @return {@code true} if this queue changed as a result of the call
*/
public boolean remove(Object o) {
int i = indexOf(o);
if (i == -1)
return false;
else {
removeAt(i);
return true;
}
}
Copy the codeQueue [I] == moved If true means that the structure has not been adjusted (to meet the heap structure) since the addition of the element, then the structure will be adjusted up. Queue [I]! If queue[I]! = Moved a value of true means that the structure has been adjusted up, and moved will be returned. (The reason for returning ‘moved’ after moving the structure up is primarily for iterator use, which I won’t cover here.)
/** * Removes the ith element from queue. * * Normally this method leaves the elements at up to i-1, * inclusive, untouched. Under these circumstances, it returns * null. Occasionally, in order to maintain the heap invariant, * it must swap a later element of the list with one earlier than * i. Under these circumstances, this method returns the element * that was previously at the end of the list and is now at some * position before i. This fact is used by iterator.remove so as to * avoid missing traversing elements. */ @SuppressWarnings("unchecked") private E removeAt(int i) { // assert i >= 0 && i < size; modCount++; int s = --size; if (s == i) // removed last element queue[i] = null; else { E moved = (E) queue[s]; queue[s] = null; siftDown(i, moved); if (queue[i] == moved) { siftUp(i, moved); if (queue[i] ! = moved) return moved; } } return null; }Copy the codeFocus on
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.
/** * Inserts item x at position k, maintaining heap invariant by * demoting x down the tree repeatedly until it is less than or * equal to its children or is a leaf. * * @param k the position to fill * @param x the item to insert */ private void siftDown(int k, E x) { if (comparator ! = null) siftDownUsingComparator(k, x); else siftDownComparable(k, x); }Copy the code
This is the general process of removing a node. This method is relatively low-level. There are other methods to remove a node in PriorityQueue, but they almost always call removeAt internally.
Conclusion:
The method and the use of the priority queue is trival, relatively to be understood, here lists only part of the daily usage, many are not as same as the previous detailed explanation, internal calls the method space too much, not one by one, for example, had to let everybody to look at the source code, in this article is to introduce to you a bit.