【Java集合源码05】PriorityQueue源码分析

缺乏、安全感 2023-01-05 05:28 266阅读 0赞

# 简介 #

PriorityQueue 一个基于优先级的无界优先级队列。优先级队列的元素默认按照升序进行排序，或者根据构造队列时提供的 Comparator 进行排序，具体取决于所使用的构造方法。该队列不允许使用 null 元素也不允许插入不可比较的对象(没有实现Comparable接口的对象)。  
PriorityQueue 队列的头指排序规则最小那个元素。如果多个元素都是最小值则随机选一个。  
PriorityQueue 是一个无界队列，但是初始的容量(实际是一个Object\[\])，随着不断向优先级队列添加元素，其容量会自动扩容，无需指定容量增加策略的细节。

PriorityQueue默认是一个容量为11的小顶堆，堆顶是最小的元素，内部通过堆排序实现有序，存储使用Object数组。

![20201205211545.png][]

# 源码 #

源码也不难，得熟悉堆排序。在小顶堆情况下，源码里有一个向上调整堆，保持当前结点的所有父节点比当前结点的值都小；向下调整堆，保持当前结点的所有子结点比当前结点的值都大。大顶堆与之相反。

## Offer/add方法 ##

1.  如果插入元素为null，就抛出异常
2.  如果size>=队列容量就扩容，扩容就是一个数组的复制，也比较简单
3.  如果是第一次插入元素，就直接插入，否则，就先上调整堆

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;
 }
 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);
 }

## peek方法 ##

size!=0,就返回堆顶元素

@SuppressWarnings("unchecked")
        public E peek() {
        
            // size!=0,就返回堆顶元素
            return (size == 0) ? null : (E) queue[0];
        }

## poll ##

// 删除堆顶元素
        @SuppressWarnings("unchecked")
        public E poll() {
        
            if (size == 0)
                return null;
            int s = --size;
            modCount++;
            // 取出堆顶元素
            E result = (E) queue[0];
            // 将最后一个置null
            E x = (E) queue[s];
            queue[s] = null;
            if (s != 0)
                // 向下调整堆
                siftDown(0, x);
            return result;
        }

## remove ##

public boolean remove(Object o) {
 
 int i = indexOf(o);
 // i = -1说明没有这个元素
 if (i == -1)
 return false;
 else {
 
 removeAt(i);
 return true;
 }
 }
 	/**
 * 删除索引i，删除完还得调整堆
 */
 @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);
 // queue[i] = moved说明先下调整不成功，尝试向上调整
 if (queue[i] == moved) {
 
 siftUp(i, moved);
 if (queue[i] != moved)
 return moved;
 }
 }
 return null;
 }

## 其他注释 ##

package java.util;
 
 import java.util.function.Consumer;
 import sun.misc.SharedSecrets;
 
 public class PriorityQueue<E> extends AbstractQueue<E>
 implements java.io.Serializable {
 
 
 private static final long serialVersionUID = -7720805057305804111L;
 
 // 默认容量
 private static final int DEFAULT_INITIAL_CAPACITY = 11;
 
 /**
 * Priority queue represented as a balanced binary heap: the two
 * children of queue[n] are queue[2*n+1] and queue[2*(n+1)]. The
 * priority queue is ordered by comparator, or by the elements'
 * natural ordering, if comparator is null: For each node n in the
 * heap and each descendant d of n, n <= d. The element with the
 * lowest value is in queue[0], assuming the queue is nonempty.
 */
 transient Object[] queue; // non-private to simplify nested class access
 
 /**
 * The number of elements in the priority queue.
 */
 private int size = 0;
 
 /**
 * The comparator, or null if priority queue uses elements'
 * natural ordering.
 */
 private final Comparator<? super E> comparator;
 
 /**
 * The number of times this priority queue has been
 * structurally modified. See AbstractList for gory details.
 */
 transient int modCount = 0; // non-private to simplify nested class access
 
 /**
 * 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 ordering} of the elements will be used.
 * @since 1.8
 */
 public PriorityQueue(Comparator<? super E> 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<? super E> comparator) {
 
 // Note: This restriction of at least one is not actually needed,
 // 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<? extends E> c) {
 
 if (c instanceof SortedSet<?>) {
 
 SortedSet<? extends E> ss = (SortedSet<? extends E>) c;
 this.comparator = (Comparator<? super E>) ss.comparator();
 initElementsFromCollection(ss);
 }
 else if (c instanceof PriorityQueue<?>) {
 
 PriorityQueue<? extends E> pq = (PriorityQueue<? extends E>) c;
 this.comparator = (Comparator<? super E>) 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<? extends E> c) {
 
 this.comparator = (Comparator<? super E>) 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<? extends E> c) {
 
 this.comparator = (Comparator<? super E>) c.comparator();
 initElementsFromCollection(c);
 }
 
 private void initFromPriorityQueue(PriorityQueue<? extends E> c) {
 
 if (c.getClass() == PriorityQueue.class) {
 
 this.queue = c.toArray();
 this.size = c.size();
 } else {
 
 initFromCollection(c);
 }
 }
 
 private void initElementsFromCollection(Collection<? extends E> c) {
 
 Object[] a = c.toArray();
 // If c.toArray incorrectly doesn't return Object[], copy it.
 if (a.getClass() != Object[].class)
 a = Arrays.copyOf(a, a.length, Object[].class);
 int len = a.length;
 if (len == 1 || this.comparator != null)
 // PriorityQueue不能存储null值
 for (int i = 0; i < len; i++)
 if (a[i] == null)
 throw new NullPointerException();
 this.queue = a;
 this.size = a.length;
 }
 
 /**
 * Initializes queue array with elements from the given Collection.
 *
 * @param c the collection
 */
 private void initFromCollection(Collection<? extends E> c) {
 
 initElementsFromCollection(c);
 // 堆排序
 heapify();
 }
 
 /**
 * The maximum size of array to allocate.
 * Some VMs reserve some header words in an array.
 * Attempts to allocate larger arrays may result in
 * OutOfMemoryError: Requested array size exceeds VM limit
 */
 private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
 
 /**
 * 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);
 }
 
 private static int hugeCapacity(int minCapacity) {
 
 if (minCapacity < 0) // overflow
 throw new OutOfMemoryError();
 return (minCapacity > MAX_ARRAY_SIZE) ?
 Integer.MAX_VALUE :
 MAX_ARRAY_SIZE;
 }
 
 /**
 * 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;
 }
 
 @SuppressWarnings("unchecked")
 public E peek() {
 
 // size!=0,就返回堆顶元素
 return (size == 0) ? null : (E) queue[0];
 }
 
 private int indexOf(Object o) {
 
 if (o != null) {
 
 for (int i = 0; i < size; i++)
 if (o.equals(queue[i]))
 return i;
 }
 return -1;
 }
 
 /**
 * 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);
 // i = -1说明没有这个元素
 if (i == -1)
 return false;
 else {
 
 removeAt(i);
 return true;
 }
 }
 
 /**
 * Version of remove using reference equality, not equals.
 * Needed by iterator.remove.
 *
 * @param o element to be removed from this queue, if present
 * @return {@code true} if removed
 * 引用相等才删除
 */
 boolean removeEq(Object o) {
 
 for (int i = 0; i < size; i++) {
 
 if (o == queue[i]) {
 
 removeAt(i);
 return true;
 }
 }
 return false;
 }
 
 /**
 * Returns {@code true} if this queue contains the specified element.
 * More formally, returns {@code true} if and only if this queue contains
 * at least one element {@code e} such that {@code o.equals(e)}.
 *
 * @param o object to be checked for containment in this queue
 * @return {@code true} if this queue contains the specified element
 */
 public boolean contains(Object o) {
 
 return indexOf(o) != -1;
 }
 
 /**
 * Returns an array containing all of the elements in this queue.
 * The elements are in no particular order.
 *
 * The returned array will be "safe" in that no references to it are
 * maintained by this queue. (In other words, this method must allocate
 * a new array). The caller is thus free to modify the returned array.
 *
 * This method acts as bridge between array-based and collection-based
 * APIs.
 *
 * @return an array containing all of the elements in this queue
 */
 public Object[] toArray() {
 
 return Arrays.copyOf(queue, size);
 }
 
 /**
 * Returns an array containing all of the elements in this queue; the
 * runtime type of the returned array is that of the specified array.
 * The returned array elements are in no particular order.
 * If the queue fits in the specified array, it is returned therein.
 * Otherwise, a new array is allocated with the runtime type of the
 * specified array and the size of this queue.
 *
 * If the queue fits in the specified array with room to spare
 * (i.e., the array has more elements than the queue), the element in
 * the array immediately following the end of the collection is set to
 * {@code null}.
 *
 * Like the {@link #toArray()} method, this method acts as bridge between
 * array-based and collection-based APIs. Further, this method allows
 * precise control over the runtime type of the output array, and may,
 * under certain circumstances, be used to save allocation costs.
 *
 * Suppose {@code x} is a queue known to contain only strings.
 * The following code can be used to dump the queue into a newly
 * allocated array of {@code String}:
 *
 * <pre> {@code String[] y = x.toArray(new String[0]);}</pre>
 *
 * Note that {@code toArray(new Object[0])} is identical in function to
 * {@code toArray()}.
 *
 * @param a the array into which the elements of the queue are to
 * be stored, if it is big enough; otherwise, a new array of the
 * same runtime type is allocated for this purpose.
 * @return an array containing all of the elements in this queue
 * @throws ArrayStoreException if the runtime type of the specified array
 * is not a supertype of the runtime type of every element in
 * this queue
 * @throws NullPointerException if the specified array is null
 */
 @SuppressWarnings("unchecked")
 public <T> T[] toArray(T[] a) {
 
 final int size = this.size;
 if (a.length < size)
 // Make a new array of a's runtime type, but my contents:
 return (T[]) Arrays.copyOf(queue, size, a.getClass());
 System.arraycopy(queue, 0, a, 0, size);
 if (a.length > size)
 a[size] = null;
 return a;
 }
 
 /**
 * Returns an iterator over the elements in this queue. The iterator
 * does not return the elements in any particular order.
 *
 * @return an iterator over the elements in this queue
 */
 public Iterator<E> iterator() {
 
 return new Itr();
 }
 
 private final class Itr implements Iterator<E> {
 
 /**
 * Index (into queue array) of element to be returned by
 * subsequent call to next.
 */
 private int cursor = 0;
 
 /**
 * 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;
 
 /**
 * A queue of elements that were moved from the unvisited portion of
 * the heap into the visited portion as a result of "unlucky" element
 * removals during the iteration. (Unlucky element removals are those
 * that require a siftup instead of a siftdown.) We must visit all of
 * the elements in this list to complete the iteration. We do this
 * after we've completed the "normal" iteration.
 *
 * We expect that most iterations, even those involving removals,
 * will not need to store elements in this field.
 */
 private ArrayDeque<E> forgetMeNot = null;
 
 /**
 * Element returned by the most recent call to next iff that
 * element was drawn from the forgetMeNot list.
 */
 private E lastRetElt = null;
 
 /**
 * 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;
 
 public boolean hasNext() {
 
 return cursor < size ||
 (forgetMeNot != null && !forgetMeNot.isEmpty());
 }
 
 @SuppressWarnings("unchecked")
 public E next() {
 
 if (expectedModCount != modCount)
 throw new ConcurrentModificationException();
 if (cursor < size)
 return (E) queue[lastRet = cursor++];
 if (forgetMeNot != null) {
 
 lastRet = -1;
 lastRetElt = forgetMeNot.poll();
 if (lastRetElt != null)
 return lastRetElt;
 }
 throw new NoSuchElementException();
 }
 
 public void remove() {
 
 if (expectedModCount != modCount)
 throw new ConcurrentModificationException();
 if (lastRet != -1) {
 
 E moved = PriorityQueue.this.removeAt(lastRet);
 lastRet = -1;
 if (moved == null)
 cursor--;
 else {
 
 if (forgetMeNot == null)
 forgetMeNot = new ArrayDeque<>();
 forgetMeNot.add(moved);
 }
 } else if (lastRetElt != null) {
 
 PriorityQueue.this.removeEq(lastRetElt);
 lastRetElt = null;
 } else {
 
 throw new IllegalStateException();
 }
 expectedModCount = modCount;
 }
 }
 
 public int size() {
 
 return size;
 }
 
 /**
 * Removes all of the elements from this priority queue.
 * The queue will be empty after this call returns.
 */
 public void clear() {
 
 modCount++;
 for (int i = 0; i < size; i++)
 queue[i] = null;
 size = 0;
 }
 // 删除堆顶元素
 @SuppressWarnings("unchecked")
 public E poll() {
 
 if (size == 0)
 return null;
 int s = --size;
 modCount++;
 // 取出堆顶元素
 E result = (E) queue[0];
 // 将最后一个置null
 E x = (E) queue[s];
 queue[s] = null;
 if (s != 0)
 // 向下调整堆
 siftDown(0, x);
 return result;
 }
 
 /**
 * 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.
 * 删除索引i，删除完还得调整堆
 */
 @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);
 // queue[i] = moved说明先下调整不成功，尝试向上调整
 if (queue[i] == moved) {
 
 siftUp(i, moved);
 if (queue[i] != moved)
 return moved;
 }
 }
 return null;
 }
 
 /**
 * 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
 * 调整堆，在k的位置插入x，直到x的父节点都比x大
 */
 private void siftUp(int k, E x) {
 
 if (comparator != null)
 siftUpUsingComparator(k, x);
 else
 siftUpComparable(k, x);
 }
 
 @SuppressWarnings("unchecked")
 private void siftUpComparable(int k, E x) {
 
 Comparable<? super E> key = (Comparable<? super E>) x;
 while (k > 0) {
 
 int parent = (k - 1) >>> 1;
 Object e = queue[parent];
 if (key.compareTo((E) e) >= 0)
 break;
 queue[k] = e;
 k = parent;
 }
 queue[k] = key;
 }
 
 @SuppressWarnings("unchecked")
 private void siftUpUsingComparator(int k, E x) {
 
 while (k > 0) {
 
 int parent = (k - 1) >>> 1;
 Object e = queue[parent];
 if (comparator.compare(x, (E) e) >= 0)
 break;
 queue[k] = e;
 k = parent;
 }
 queue[k] = x;
 }
 
 /**
 * 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
 * 调整堆，在k的位置插入x，直到x的子孩子都比x小
 */
 private void siftDown(int k, E x) {
 
 // 默认调整规则
 if (comparator != null)
 siftDownUsingComparator(k, x);
 else
 siftDownComparable(k, x);
 }
 
 @SuppressWarnings("unchecked")
 private void siftDownComparable(int k, E x) {
 
 Comparable<? super E> key = (Comparable<? super E>)x;
 int half = size >>> 1; // loop while a non-leaf
 while (k < half) {
 
 int child = (k << 1) + 1; // assume left child is least
 Object c = queue[child];
 int right = child + 1;
 if (right < size &&
 ((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
 c = queue[child = right];
 if (key.compareTo((E) c) <= 0)
 break;
 queue[k] = c;
 k = child;
 }
 queue[k] = key;
 }
 
 @SuppressWarnings("unchecked")
 private void siftDownUsingComparator(int k, E x) {
 
 int half = size >>> 1;
 while (k < half) {
 
 // 左孩子是2k + 1
 int child = (k << 1) + 1;
 Object c = queue[child];
 // 右孩子是2k + 2
 int right = child + 1;
 // 对比左孩子和右孩子大小，取最小值
 if (right < size &&
 comparator.compare((E) c, (E) queue[right]) > 0)
 c = queue[child = right];
 // 如果x比c小就跳出循环
 if (comparator.compare(x, (E) c) <= 0)
 break;
 // 保持堆顶最小
 queue[k] = c;
 k = child;
 }
 queue[k] = x;
 }
 
 /**
 * Establishes the heap invariant (described above) in the entire tree,
 * assuming nothing about the order of the elements prior to the call.
 */
 @SuppressWarnings("unchecked")
 private void heapify() {
 
 for (int i = (size >>> 1) - 1; i >= 0; i--)
 siftDown(i, (E) queue[i]);
 }
 
 /**
 * Returns the comparator used to order the elements in this
 * queue, or {@code null} if this queue is sorted according to
 * the {@linkplain Comparable natural ordering} of its elements.
 *
 * @return the comparator used to order this queue, or
 * {@code null} if this queue is sorted according to the
 * natural ordering of its elements
 */
 public Comparator<? super E> comparator() {
 
 return comparator;
 }
 
 /**
 * Saves this queue to a stream (that is, serializes it).
 *
 * @serialData The length of the array backing the instance is
 * emitted (int), followed by all of its elements
 * (each an {@code Object}) in the proper order.
 * @param s the stream
 */
 private void writeObject(java.io.ObjectOutputStream s)
 throws java.io.IOException {
 
 // Write out element count, and any hidden stuff
 s.defaultWriteObject();
 
 // Write out array length, for compatibility with 1.5 version
 s.writeInt(Math.max(2, size + 1));
 
 // Write out all elements in the "proper order".
 for (int i = 0; i < size; i++)
 s.writeObject(queue[i]);
 }
 
 /**
 * Reconstitutes the {@code PriorityQueue} instance from a stream
 * (that is, deserializes it).
 *
 * @param s the stream
 */
 private void readObject(java.io.ObjectInputStream s)
 throws java.io.IOException, ClassNotFoundException {
 
 // Read in size, and any hidden stuff
 s.defaultReadObject();
 
 // Read in (and discard) array length
 s.readInt();
 
 SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, size);
 queue = new Object[size];
 
 // Read in all elements.
 for (int i = 0; i < size; i++)
 queue[i] = s.readObject();
 
 // Elements are guaranteed to be in "proper order", but the
 // spec has never explained what that might be.
 heapify();
 }
 
 /**
 * Creates a <a href="Spliterator.html#binding">late-binding</a>
 * and fail-fast {@link Spliterator} over the elements in this
 * queue.
 *
 * The {@code Spliterator} reports {@link Spliterator#SIZED},
 * {@link Spliterator#SUBSIZED}, and {@link Spliterator#NONNULL}.
 * Overriding implementations should document the reporting of additional
 * characteristic values.
 *
 * @return a {@code Spliterator} over the elements in this queue
 * @since 1.8
 */
 public final Spliterator<E> spliterator() {
 
 return new PriorityQueueSpliterator<E>(this, 0, -1, 0);
 }
 
 static final class PriorityQueueSpliterator<E> implements Spliterator<E> {
 
 /*
 * This is very similar to ArrayList Spliterator, except for
 * extra null checks.
 */
 private final PriorityQueue<E> pq;
 private int index; // current index, modified on advance/split
 private int fence; // -1 until first use
 private int expectedModCount; // initialized when fence set
 
 /** Creates new spliterator covering the given range */
 PriorityQueueSpliterator(PriorityQueue<E> pq, int origin, int fence,
 int expectedModCount) {
 
 this.pq = pq;
 this.index = origin;
 this.fence = fence;
 this.expectedModCount = expectedModCount;
 }
 
 private int getFence() {
 // initialize fence to size on first use
 int hi;
 if ((hi = fence) < 0) {
 
 expectedModCount = pq.modCount;
 hi = fence = pq.size;
 }
 return hi;
 }
 
 public PriorityQueueSpliterator<E> trySplit() {
 
 int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
 return (lo >= mid) ? null :
 new PriorityQueueSpliterator<E>(pq, lo, index = mid,
 expectedModCount);
 }
 
 @SuppressWarnings("unchecked")
 public void forEachRemaining(Consumer<? super E> action) {
 
 int i, hi, mc; // hoist accesses and checks from loop
 PriorityQueue<E> q; Object[] a;
 if (action == null)
 throw new NullPointerException();
 if ((q = pq) != null && (a = q.queue) != null) {
 
 if ((hi = fence) < 0) {
 
 mc = q.modCount;
 hi = q.size;
 }
 else
 mc = expectedModCount;
 if ((i = index) >= 0 && (index = hi) <= a.length) {
 
 for (E e;; ++i) {
 
 if (i < hi) {
 
 if ((e = (E) a[i]) == null) // must be CME
 break;
 action.accept(e);
 }
 else if (q.modCount != mc)
 break;
 else
 return;
 }
 }
 }
 throw new ConcurrentModificationException();
 }
 
 public boolean tryAdvance(Consumer<? super E> action) {
 
 if (action == null)
 throw new NullPointerException();
 int hi = getFence(), lo = index;
 if (lo >= 0 && lo < hi) {
 
 index = lo + 1;
 @SuppressWarnings("unchecked") E e = (E)pq.queue[lo];
 if (e == null)
 throw new ConcurrentModificationException();
 action.accept(e);
 if (pq.modCount != expectedModCount)
 throw new ConcurrentModificationException();
 return true;
 }
 return false;
 }
 
 public long estimateSize() {
 
 return (long) (getFence() - index);
 }
 
 public int characteristics() {
 
 return Spliterator.SIZED | Spliterator.SUBSIZED | Spliterator.NONNULL;
 }
 }
 }

--------------------

**欢迎关注我的公众号呦，率先更新内容，并且后续还有一些源码级的免费教程推出。**

![gzh.jpg][]

[20201205211545.png]: /images/20221119/47f30c6f1a44431fa7e8b854435379b2.png
[gzh.jpg]: /images/20221119/e61a3d4ecec8498d815c316bdc1fd87d.png