Java collection source code parsing series:
- Unpacking decoding Java collection source code overview
- Decoding Java Collection source code Collection of three systems
- Iterator for decoding Java collection source code
- Unpacking Java collection source code ArrayList
- Unpack the LinkedList of Java collection source code
- Decode HashMap of Java collection source code
- Decode Java collection source code Hashtable
- Unlink decode Java collection source code LinkedHashMap
- Decode Java collection source code PriorityQueue
- ArrayDeque decoding Java collection source code
features
-
Null is not allowed.
-
Unbounded priority queue based on small top heap, top = queue head.
-
Sort based on element comparability (either implement Comparable; Either specify a Comparator.
-
Iterators are not guaranteed to traverse elements in a particular order
Arrays.sort(pq.toarray ()) can be used for sequential traversal.
-
The thread is unsafe and can be synchronized using PriorityBlockingQueue.
-
The efficiency of
Methods of joining and leaving a team (offer, poll, remove, add) provide O(log(n)) time;
Linear time of remove(Object) and Contains (Object) methods;
Fixed time retrieval methods (peek, Element, size).
The source code
The initial capacity is 11. The capacity cannot be less than 1.
The element must implement Comparable, or the queue constructor must specify a Comparator.
Capacity expansion: If the value is less than 64, the value is doubled and then + 2 for each capacity expansion. Otherwise, 50% expansion.
The constructor
The data structure is Object[], and the capacity is shown above.
The interior is implemented through the small top heap, so there are requirements for elements or comparators.
When migrating from an ordered collection, the original order is not changed; Otherwise, rebuild the small top heap according to the rules.
Comparable or Comparator values are Comparable and are not Comparable in any natural sense.
Let’s say 2 is greater than 1.
public class PriorityQueue<E> extends AbstractQueue<E> implements java.io.Serializable {
private static final int DEFAULT_INITIAL_CAPACITY = 11;
/** * represents the priority queue of the balanced binary heap: the two children of queue [n] are Queue [2 * n + 1] and queue [2 * (n + 1)]. * If the comparator is null, the priority queue is sorted in the natural order of the comparator or elements: for each node n in the heap and each descendant D of n, n <= d. * Assuming the queue is non-empty, the element with the lowest value is in queue [0] */
transient Object[] queue; // non-private to simplify nested class access
int size;
// Specifies the comparator that takes precedence over the element even if it implements Comparable
private final Comparator<? super E> comparator;
transient int modCount; // non-private to simplify nested class access
public PriorityQueue(a) {
this(DEFAULT_INITIAL_CAPACITY, null);
}
public PriorityQueue(int initialCapacity) {
this(initialCapacity, null);
}
public PriorityQueue(Comparator<? super E> comparator) {
this(DEFAULT_INITIAL_CAPACITY, comparator);
}
public PriorityQueue(int initialCapacity,
Comparator<? super E> comparator) {
// Specify an initial capacity of at least 1, itself for compatibility with 1.5
if (initialCapacity < 1)
throw new IllegalArgumentException();
this.queue = new Object[initialCapacity];
this.comparator = comparator;
}
/** * If it is an ordered set of SortedSet or PriorityQueue, migrate in the original order */ otherwise build the small top heap according to the Comparable of the elements */
public PriorityQueue(Collection<? extends E> c) {
if (c instanceofSortedSet<? >) { SortedSet<? extends E> ss = (SortedSet<? extends E>) c;this.comparator = (Comparator<? super E>) ss.comparator();
initElementsFromCollection(ss);
}
else if (c instanceofPriorityQueue<? >) { PriorityQueue<? extends E> pq = (PriorityQueue<? extends E>) c;this.comparator = (Comparator<? super E>) pq.comparator();
initFromPriorityQueue(pq);
}
else {
this.comparator = null;
// Non-ordered setinitFromCollection(c); }}public PriorityQueue(PriorityQueue<? extends E> c) {
this.comparator = (Comparator<? super E>) c.comparator();
initFromPriorityQueue(c);
}
public PriorityQueue(SortedSet<? extends E> c) {
this.comparator = (Comparator<? super E>) c.comparator();
initElementsFromCollection(c);
}
/** * Ensure queue[0] exists to help peek() and poll() ** /
private static Object[] ensureNonEmpty(Object[] es) {
return (es.length > 0)? es :new Object[1];
}
private void initFromPriorityQueue(PriorityQueue<? extends E> c) {
if (c.getClass() == PriorityQueue.class) {
this.queue = ensureNonEmpty(c.toArray());
this.size = c.size();
} else{ initFromCollection(c); }}private void initElementsFromCollection(Collection<? extends E> c) {
Object[] es = c.toArray();
int len = es.length;
// If c.toArray incorrectly doesn't return Object[], copy it.
if(es.getClass() ! = Object[].class) es = Arrays.copyOf(es, len, Object[].class);if (len == 1 || this.comparator ! =null)
for (Object e : es)
if (e == null)
// The check element is not null
throw new NullPointerException();
// Otherwise, the limit will not be NULL for self-comparison during subsequent small top heap building
this.queue = ensureNonEmpty(es);
this.size = len;
}
private void initFromCollection(Collection<? extends E> c) {
initElementsFromCollection(c);
heapify();
}
Unlike heap sort, you only need to build the heap. You don't need to get the whole ordered set */
private void heapify(a) {
final Object[] es = queue;
int n = size, i = (n >>> 1) - 1;
final Comparator<? super E> cmp;
// Screen down
if ((cmp = comparator) == null)
for (; i >= 0; i--)
siftDownComparable(i, (E) es[i], es, n);
else
for (; i >= 0; i--) siftDownUsingComparator(i, (E) es[i], es, n, cmp); }}Copy the codeHeapify () is the logic for building the small top heap, press the not table first, and look at it later.
Single data operation
public boolean add(E e) {
return offer(e);
}
public boolean offer(E e) {
if (e == null)
throw new NullPointerException();
modCount++;
int i = size;
if (i >= queue.length)
grow(i + 1);
siftUp(i, e);
size = i + 1;
return true;
}
public E peek(a) {
return (E) queue[0];
}
public boolean remove(Object o) {
int i = indexOf(o);
if (i == -1)
return false;
else {
removeAt(i);
return true; }}void removeEq(Object o) {
final Object[] es = queue;
for (int i = 0, n = size; i < n; i++) {
if (o == es[i]) {
removeAt(i);
break; }}}E removeAt(int i) {
// assert i >= 0 && i < size;
final Object[] es = queue;
modCount++;
int s = --size;
if (s == i) // removed last element
es[i] = null;
else {
E moved = (E) es[s];
// After I is removed, fill the last bit to I and adjust the heap
// The size of the array is set to null
es[s] = null;
// Because it is from the last bit up, it has priority to sink (think it is less than the current position of the child)
siftDown(i, moved);
if (es[i] == moved) {
// There is no adjustment, then adjust up (maybe this subtree is small)
siftUp(i, moved);
if(es[i] ! = moved)// 'moved' may not be iterated in case iterators are iterated sequentially because of adjustments.
// So it is returned to the caller for processing (in a new ArrayQueue, after traversing the original queue, the new queue continues)
returnmoved; }}return null;
}
public E poll(a) {
final Object[] es;
final E result;
if ((result = (E) ((es = queue)[0))! =null) {
modCount++;
final int n;
final E x = (E) es[(n = --size)];
es[n] = null;
if (n > 0) {
final Comparator<? super E> cmp;
// The last bit is placed at the top of the heap, so instead of removing the specified bit (down or up first), you just need to adjust it down
if ((cmp = comparator) == null)
siftDownComparable(0, x, es, n);
else
siftDownUsingComparator(0, x, es, n, cmp); }}return result;
}
Copy the codePile of adjustment
As you can see, whether the heap is built, or elements are added or removed, heap adjustments are definitely involved.
There are two main ones:
- SiftUp: Elements are compared and adjusted to their parent.
- Queue [size-1]), so need to go up.
- SiftDown: Elements are compared and adjusted to their children (smaller left and right).
- The queue heads out (queue[0]), so it needs to go down.
If the middle element is removed and replaced from the last, it is generally considered that the value is still smaller, so siftDown takes precedence over siftUp if there is no change.
There are also two methods xxxComparable or xxxUsingComparator, depending on how you compare.
/** * raises an element to its parent, or even to the root */
private void siftUp(int k, E x) {
if(comparator ! =null)
siftUpUsingComparator(k, x, queue, comparator);
else
siftUpComparable(k, x, queue);
}
private static <T> void siftUpComparable(int k, T x, Object[] es) {
Comparable<? super T> key = (Comparable<? super T>) x;
while (k > 0) {
// parent specifies the insertion position of the parent
int parent = (k - 1) > > >1;
Object e = es[parent];
if (key.compareTo((T) e) >= 0)
break;
// Change the parent level
es[k] = e;
// Continue the comparison
k = parent;
}
es[k] = key;
}
private static <T> void siftUpUsingComparator(
int k, T x, Object[] es, Comparator<? super T> cmp) {
while (k > 0) {
int parent = (k - 1) > > >1;
Object e = es[parent];
if (cmp.compare(x, (T) e) >= 0)
break;
es[k] = e;
k = parent;
}
es[k] = x;
}
/** * An element sinks to a child, or even a leaf node */
private void siftDown(int k, E x) {
if(comparator ! =null)
siftDownUsingComparator(k, x, queue, size, comparator);
else
siftDownComparable(k, x, queue, size);
}
private static <T> void siftDownComparable(int k, T x, Object[] es, int n) {
// assert n > 0;
Comparable<? super T> key = (Comparable<? super T>)x;
int half = n >>> 1; // loop while a non-leaf
while (k < half) {
// select "left child"
int child = (k << 1) + 1; // assume left child is least
Object c = es[child];
int right = child + 1;
if (right < n &&
((Comparable<? super T>) c).compareTo((T) es[right]) > 0)
// Of the left and right twins, take the smaller one
c = es[child = right];
if (key.compareTo((T) c) <= 0)
break;
// The son is smaller than the father
es[k] = c;
Push down to the bottom of the tree until you reach the leaves
k = child;
}
es[k] = key;
}
private static <T> void siftDownUsingComparator(
int k, T x, Object[] es, int n, Comparator<? super T> cmp) {
// assert n > 0;
int half = n >>> 1;
while (k < half) {
int child = (k << 1) + 1;
Object c = es[child];
int right = child + 1;
if (right < n && cmp.compare((T) c, (T) es[right]) > 0)
c = es[child = right];
if (cmp.compare(x, (T) c) <= 0)
break;
es[k] = c;
k = child;
}
es[k] = x;
}
Copy the codeBatch of removing
public boolean removeIf(Predicate<? super E> filter) {
Objects.requireNonNull(filter);
return bulkRemove(filter);
}
public boolean removeAll(Collection
c) {
Objects.requireNonNull(c);
return bulkRemove(e -> c.contains(e));
}
public boolean retainAll(Collection
c) {
Objects.requireNonNull(c);
returnbulkRemove(e -> ! c.contains(e)); }// A tiny bit set implementation
private static long[] nBits(int n) {
return new long[((n - 1) > >6) + 1];
}
private static void setBit(long[] bits, int i) {
bits[i >> 6] | =1L << i;
}
private static boolean isClear(long[] bits, int i) {
return (bits[i >> 6] & (1L << i)) == 0;
}
/** Implementation of bulk remove methods. */
private boolean bulkRemove(Predicate<? super E> filter) {
final int expectedModCount = ++modCount;
final Object[] es = queue;
final int end = size;
int i;
// Optimize for initial run of survivors
for (i = 0; i < end && ! filter.test((E) es[i]); i++) ;if (i >= end) {
if(modCount ! = expectedModCount)throw new ConcurrentModificationException();
return false;
}
// Use bitmap to find the elements that match the conditions, delete the elements in batches.
// Avoid multiple adjustments
final int beg = i;
final long[] deathRow = nBits(end - beg);
deathRow[0] = 1L; // set bit 0
for (i = beg + 1; i < end; i++)
if (filter.test((E) es[i]))
setBit(deathRow, i - beg);
if(modCount ! = expectedModCount)throw new ConcurrentModificationException();
int w = beg;
for (i = beg; i < end; i++)
if (isClear(deathRow, i - beg))
es[w++] = es[i];
for (i = size = w; i < end; i++)
es[i] = null;
// Rebuild the heap
heapify();
return true;
}
Copy the codecapacity
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private void grow(int minCapacity) {
int oldCapacity = queue.length;
// Double size if small; else grow by 50%
// If the value is less than 64, increase the value by 2. Otherwise 50% expansion
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);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
Copy the codeThe iterator
Iterators allow elements to be removed. Removing elements, however, causes heap adjustments.
When the last element takes its place, an upward adjustment to the visited location can occur, so removeAt needs to return the adjusted element.
The iterator needs a new container to continue iterating over the elements and even removing them.
private final class Itr implements Iterator<E> {
/** * Index (into queue array) of element to be returned by * subsequent call to next. */
private int cursor;
/** * Index of element returned by most recent call to next, * unless that element came from the forgetMeNot list. * Set to -1 if element is deleted by a call to remove. */
private int lastRet = -1;
/** * The element queue is moved from the unaccessed part of the heap to the accessed part due to an "unfortunate" element deletion during iteration. * (The unfortunate element deletions are those that move down to the top, i.e., siftUp) * We must access all elements in this list to complete the iteration. * We do this after completing the "normal" iteration (that is, running out of the original iterator). * We expect that most iterations, even those involving deletion, do not need to store elements in this field. * is a sequential bidirectional queue */
private ArrayDeque<E> forgetMeNot;
/**
* Element returned by the most recent call to next iff that
* element was drawn from the forgetMeNot list.
* 类同于 lastRet, 不过来自于新队列 forgetMeNot, 所以不是根据索引存储.
*/
private E lastRetElt;
/** * The modCount value that the iterator believes that the backing * Queue should have. If this expectation is violated, the iterator * has detected concurrent modification. */
private int expectedModCount = modCount;
Itr() {} // prevent access constructor creation
public boolean hasNext(a) {
// Determine both queues simultaneously
returncursor < size || (forgetMeNot ! =null && !forgetMeNot.isEmpty());
}
public E next(a) {
if(expectedModCount ! = modCount)throw new ConcurrentModificationException();
if (cursor < size)
return (E) queue[lastRet = cursor++];
if(forgetMeNot ! =null) {
lastRet = -1;
// fetch from the new queue
lastRetElt = forgetMeNot.poll();
if(lastRetElt ! =null)
return lastRetElt;
}
throw new NoSuchElementException();
}
public void remove(a) {
if(expectedModCount ! = modCount)throw new ConcurrentModificationException();
if(lastRet ! = -1) {
E moved = PriorityQueue.this.removeAt(lastRet);
// Set to -1 because the most recent traversal was removed
lastRet = -1;
if (moved == null)
// Remove the complement mechanism, so that the current location can be accessed again
cursor--;
else {
// Moved Is not empty, indicating an upward adjustment
if (forgetMeNot == null)
// Is a sequential bidirectional queue
forgetMeNot = newArrayDeque<>(); forgetMeNot.add(moved); }}else if(lastRetElt ! =null) {
// Remove from the new queue
PriorityQueue.this.removeEq(lastRetElt);
lastRetElt = null;
} else {
throw newIllegalStateException(); } expectedModCount = modCount; }}Copy the code