Java 集合深入理解 （九） ：优先队列（PriorityQueue）之源码解读，及最小顶堆实现研究_priorityqueue<>((i1, i2) -> a[i2] - a[i1]);

前言

queue 接口
队列就是一个先入先出（FIFO）的数据结构
AbstractQueue类
也是继承自AbstractCollection 并实现queue接口的，在集合基础增加一些队列自带的方法 的基础实现
PriorityQueue类
继承AbstractQueue ，用object数组存储数组，通过二叉小顶堆实现，用一棵完全二叉树表示。（对于平常我们研究的树，大部分都是链表实现的，对于堆实现还是很有研究的意义）
这种实现：
它的出队顺序与元素的优先级有关，对PriorityQueue调用remove()或poll()方法，返回的总是优先级最高的元素。而对于什么是优先级最高的元素，在数组中看起来不是最顺序的。

先写一个例子

public static void main(String[] args) {
		PriorityQueue<Integer> q = new PriorityQueue<>();
        q.offer(3);
        q.offer(1);
        q.offer(2);
        System.out.println(q.poll()); // 1
        System.out.println(q.poll()); // 2
        System.out.println(q.poll()); // 3
        System.out.println(q.poll()); // null,因为队列为空
    }
1
2
3
4
5
6
7
8
9
10

看例子 默认会将integer在offer的时候就进行排序，自动插入到合适的位置保证队列有序。

PriorityQueue 的注释

	/**
	*基于优先级堆的无限优先级{@linkplain Queue}。
	*优先级队列的元素根据它们的优先级排序
	*{@linkplain Comparable natural ordering}，或通过{@link Comparator}
	*在队列构造时提供，具体取决于所使用的构造函数用过的。优先级队列不允许{@code null}元素。
	*依赖于自然排序的优先级队列也不允许插入不可比较的对象（这样做可能会导致
	*{@code ClassCastException}）。
	*<p>这个队列的<em>头是<em>最少的<em>元素
	*关于指定的顺序。如果有多个元素为了最小的价值，头部是其中的一个元素——领带是
	*任意破坏。队列检索操作{@code poll}，{@code remove}、{@code peek}和{@code element}访问
	*位于队列头部的元素。
	*<p>优先级队列是无界的，但具有内部
	*<i>容量</i>控制用于存储队列中的元素。它总是至少和队列一样大
	*大小。当元素添加到优先级队列时，它的容量自动增长。增长政策的细节并不清楚指定。
	*<p>这个类及其迭代器实现了
	*<em>可选的{@link集合}和{@link集合的方法迭代器}接口。方法{@link中提供的迭代器
	*#iterator（）}不能保证遍历按任何特定顺序排列的优先级队列。如果您需要订购
	*遍历时，请考虑使用{@code Arrays.sort（pq.toArray（））}。
	*<p><strong>请注意，此实现不同步。</strong>多个线程不应访问{@code PriorityQueue}
	*如果任何线程修改队列，则同时执行。相反，使用线程安全的{@link
	*java.util.concurrent.PriorityBlockingQueue}类。
	*<p>实施说明：此实施提供
	*O（log（n））排队和出列方法的时间
	*（{@code offer}、{@code poll}、{@code remove（）}和{@code add}）；
	*{@code remove（Object）}和{@code contains（Object）}的线性时间
	*方法；检索方法的时间常数（{@code peek}、{@code element}和{@code size}）。
	* <p>This class is a member of the
	* <a href="{@docRoot}/../technotes/guides/collections/index.html">
	* Java Collections Framework</a>.
	*
	* @since 1.5
	* @author Josh Bloch, Doug Lea
	* @param <E> the type of elements held in this collection
	*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

总结注释上面的意思 Java1.5中引入的
1.基于优先级堆进行排序
2.优先级队列不允许{@code null}元素 依赖于自然排序的优先级队列也不允许插入不可比较的对象 就可能导致ClassCastException异常
3.优先级队列是无界的，但具有内部 容量控制用于存储队列中的元素。它总是至少和队列一样大
4.此实现不同步如果想使用线程安全的，则使用PriorityBlockingQueue类

实现原理

可以用一棵完全二叉树表示（任意一个非叶子节点的权值，都不大于其左右子节点的权值），也就意味着可以通过数组来作为PriorityQueue的底层实现。

根据例图来看
PriorityQueue的底层实现为平衡二进制堆的优先级队列：
队列[n]的子级是队列[2n+1]和队列[2（n+1）]。
leftNo = [2n+1]
rightNo = [2（n+1）]
队列n也就是父节点
通过上述2个公式，可以轻易计算出某个节点的父节点以及子节点的下标。这也就是为什么可以直接用数组来存储堆的原因。
PriorityQueue_的peek()和element操作是常数时间，add(), offer(), 无参数的remove()以及poll()方法的时间复杂度都是_log(N) 。
不理解_log(N) 参考
时间复杂度 O(log n) 意味着什么

属性分析

  private static final int DEFAULT_INITIAL_CAPACITY = 11;
 /**
    *表示为平衡二进制堆的优先级队列：队列[n]的子级是队列[2*n+1]和队列[2*（n+1）]。这个
    *优先级队列由比较器或元素的自然排序，如果比较器为空：对于堆和n的每个后代d，n<=d。具有
    *最小值在队列[0]中，假设该队列为非空。
     */
    transient Object[] queue; // 非私有以简化嵌套类访问

    /**
     * 优先级队列中的元素数。
     */
    private int size = 0;

    /**
     * 比较器，如果优先级队列使用元素
     * natural ordering.
     */
    private final Comparator<? super E> comparator;
  /**
     * 此优先级队列被删除的次数
     * <i> 结构上修改的</i>。请参见抽象列表。
     */
    transient int modCount = 0; // 非私有以简化嵌套类访问

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

默认容量

默认容量为11，该容量是初始化容器时进行设置的

transient修饰的变量不参与序列化和反序列化
在序列化时，定义了两个方法writeObject和readObject，实现了自己可控制的序列化，而达到定制的效果，也就是不跟据queue的大小进行序列化，而是根据 size进行的

   /**
     * 将此队列保存到流中（即序列化它）。
     *
     * @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 {
        // 写下元素计数和任何隐藏的东西
        s.defaultWriteObject();

        // 写出数组长度，以便与1.5版本兼容
        s.writeInt(Math.max(2, size + 1));

        // 按“适当的顺序”写出所有的内容。
        for (int i = 0; i < size; i++)
            s.writeObject(queue[i]);
    }

 /**
     * 从流中重建{@code PriorityQueue}实例
     * (that is, deserializes it).
     *
     * @param s the stream
     */
    private void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {
        // 阅读的大小，以及任何隐藏的东西
        s.defaultReadObject();

        // 读入（和丢弃）数组长度
        s.readInt();

        queue = new Object[size];

        // 读入所有元素。
        for (int i = 0; i < size; i++)
            queue[i] = s.readObject();

        // 元素保证“有序”，但
        // spec从未解释过这可能是什么
        heapify();
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

理解作者所写的平衡二进制堆的优先级队列
先从什么是堆说起
堆是一种非线性结构，（分析堆的数组实现）可以把堆看作一个数组，也可以被看作一个完全二叉树，通俗来讲堆其实就是利用完全二叉树的结构来维护的一维数组
按照堆的特点可以把堆分为大顶堆和小顶堆
大顶堆：每个结点的值都大于或等于其左右孩子结点的值
小顶堆：每个结点的值都小于或等于其左右孩子结点的值
堆的这种特性非常的有用，堆常常被当做优先队列使用，因为可以快速的访问到“最重要”的元素

优先级队列
是由小顶堆实现的数据结构。

构造方法

1. 不带参数的构造方法
   设置默认的容量1 以及默认的Comparator
2. 带默认容量的构造方法，
   设置默认的Comparator
3. 指定Comparator和容量
4. PriorityQueue 构造方法中放集合
   利用initElementsFromCollection 初始化方法初始化数据，并赋值pq.comparator()，没有构造器则设置为null

public PriorityQueue() {
        this(DEFAULT_INITIAL_CAPACITY, null);
    }
 public PriorityQueue(int initialCapacity) {
        this(initialCapacity, null);
    }
  public PriorityQueue(Comparator<? super E> comparator) {
        this(DEFAULT_INITIAL_CAPACITY, comparator);
    }
/**
     * 创建具有指定初始容量的{@code PriorityQueue}
     * 它根据指定的比较器对其元素进行排序。
     *
     * @param  initialCapacity此优先级队列的初始容量
     * @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) {
        // 注意：实际上不需要至少一个的限制，
        // 但1.5的兼容性仍在继续
        if (initialCapacity < 1)
            throw new IllegalArgumentException();
        this.queue = new Object[initialCapacity];
        this.comparator = comparator;
    }
 /**
     * 创建包含中元素的{@code PriorityQueue}
     * 指定的集合。如果指定的集合是
     * 一个{@link SortedSet}或者是另一个{@code PriorityQueue}，这个
     * 优先级队列将按照相同的顺序排序。否则，此优先级队列将根据
     * 元素的{@linkplain可比自然排序}。
     *
     * @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);
        }
    }
  private void initElementsFromCollection(Collection<? extends E> c) {
        Object[] a = c.toArray();
        // 如果c.toArray不正确地返回Object[]，请复制它。
        if (a.getClass() != Object[].class)
            a = Arrays.copyOf(a, a.length, Object[].class);
        int len = a.length;
        if (len == 1 || this.comparator != null)
            for (int i = 0; i < len; i++)
                if (a[i] == null)
                    throw new NullPointerException();
        this.queue = a;
        this.size = a.length;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

1. initElementsFromCollection方法
   不调整数据顺序，直接将 初始化 集合中的数据赋值给属性queue 和size

//initFromCollection 调整数据结构

  /**
     * 在整个树中建立堆不变量（如上所述），
     * 在调用之前不考虑元素的顺序。
     */
    @SuppressWarnings("unchecked")
    private void heapify() {
        for (int i = (size >>> 1) - 1; i >= 0; i--)
            siftDown(i, (E) queue[i]);
    }
  /**
     * 在位置k处插入项目x，保持堆不变
     * 重复将x降级到树下，直到它小于或等于
     * 等于它的孩子或是一片叶子。
     *
     * @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);
    }
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

siftDown方法
这就是保持堆不变 做调整树的方法，在remove()和poll() 方法中也会调用的，这里先不 深究

add 和offer 方法

  /**
     * 将指定的元素插入此优先级队列。
     *
     * @return {@code true} (as specified by {@link Collection#add})
     * @throws ClassCastException 如果指定的元素不能
     *         与当前在此优先级队列中的元素进行比较
     *         根据优先级队列的顺序
     * @throws NullPointerException if the specified element is null
     */
    public boolean add(E e) {
        return offer(e);
    }
     /**
     * 将指定的元素插入此优先级队列。
     *
     * @return {@code true} (as specified by {@link Queue#offer})
     * @throws ClassCastException 如果指定的元素不能
     *         与当前在此优先级队列中的元素进行比较
     *         根据优先级队列的顺序
     * @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;
    }
  /**
     * 增加阵列的容量。
     *
     * @param 最小容量所需的最小容量
     */
    private void grow(int minCapacity) {
        int oldCapacity = queue.length;
        // 两倍大小，如果小；其他增长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);
    }
    
//arrylist中代码
private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }
 private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // 有溢出意识的代码
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

从上面的代码分析

• offer 方法 如果添加e值为null则直接抛出 NullPointerException 异常
• i >= queue.length 才判断需要扩展队列长度，当前size只要等于队列的大小就进行扩容，
  这个可以arrayList中的动态扩容比对看一下
• arraylist中会先从size加+1判断 在和默认容量比较取最大容量，在与数组大小对比扩容，并扩展老容量的50%，其实都是达到动态扩容的效果
• PriorityQueue扩容则直接判断老容量是否小于64，然后在采用不同的扩容方式，小于64直接扩容两倍，大于64，直接扩容50%
• 只有当所需最小的容量大于最大容量，才使用最小容量去计算新容量
  PriorityQueue的动态扩容
  

siftUp方法

  /**
     * 在位置k处插入项x，保持堆不变
     * 在树上提升x，直到它大于或等于
     * 它的父级，或者是根。
     *
     * 简化和加速强制和比较。这个
     * 可比版本和比较版本分为不同的版本
     * 其他方面相同的方法(类似于siftDown。）
     *
     * @param k要填补的职位
     * @param x the item to insert
     */
    private void siftUp(int k, E x) {
        if (comparator != null)
            siftUpUsingComparator(k, x);
        else
            siftUpComparable(k, x);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

这是一个最小根堆，从某个节点开始往上对比，一旦父节点比它大，则交换，直到比它小为止。 这可能比较难理解，就用一个图画来展示。

从末尾添加一个节点

往上和父节点比较交换数据

完成交换实现代码
对于没有传入Comparator 的
1.默认需要传入对象需要支持Comparable，不然会出现转换异常，并且，对比也是调用的是对象的compareTo方法
2. 在这里 k是size, 这个公式是求左右节点的2*（n+1） 的变形
从k指定的位置开始，将x逐层与当前点的parent进行比较并交换，直到满足x >= queue[parent]为止

  @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;//parentNo = (nodeNo-1)/2
            Object e = queue[parent];
            if (key.compareTo((E) e) >= 0)
                break;
            queue[k] = e;
            k = parent;
        }
        queue[k] = key;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13

这就是整个 add offer操作，重要的一点主要是 利用最小堆调整数据位置的

peek 和indexOf和element()方法

** peek 方法 获取到 第一个数据数据，先进先出 **

 public E peek() {
        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;
    }
1
2
3
4
5
6
7
8
9
10
11
12

AbstractQueue 类中element方法
当没有数组则抛NoSuchElementException异常

   public E element() {
        E x = peek();
        if (x != null)
            return x;
        else
            throw new NoSuchElementException();
    }
1
2
3
4
5
6
7

poll()和remove（）方法

remove()和poll()方法的语义也完全相同，都是获取并删除队首元素，区别是前者当方法失败时前者抛出异常，后者返回null。由于删除操作会改变队列的结构，为维护小顶堆的性质，需要进行必要的调整。

AbstractQueue 中实现remove 方法

  public E remove() {
        E x = poll();
        if (x != null)
            return x;
        else
            throw new NoSuchElementException();
    }
1
2
3
4
5
6
7

数据为空则抛出NoSuchElementException异常

poll方法源码

  @SuppressWarnings("unchecked")
    public E poll() {
        if (size == 0)
            return null;
        int s = --size;
        modCount++;
        E result = (E) queue[0];
        E x = (E) queue[s];
        queue[s] = null;
        if (s != 0)
            siftDown(0, x);
        return result;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13

modCount 变量加+1，size -1 将头数据给获取到返回。

shfitdown 方法
该方法的作用是从k指定的位置开始，将x逐层向下与当前点的左右孩子中较小的那个交换，直到x小于或等于左右孩子中的任何一个为止。 相对于新增会麻烦一点

1.头元素取出

将最后元素拿到赋值给头元素

与小子节点进行比较，大于根节点进行交换赋值


源码实现

 @SuppressWarnings("unchecked")
    private void siftDownUsingComparator(int k, E x) {
        int half = size >>> 1; //size /2 取得一部分
        while (k < half) { 
            int child = (k << 1) + 1;  //[2*n+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;
            k = child;
        }
        queue[k] = x;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

左节点大于右节点 ，则取右节点作为循环节点，也就是取左右节点中小的节点

remove(Object o) 方法

/**
     * 从此队列中删除指定元素的单个实例，
     * 如果有。更正式地说，删除元素{@code e}，例如
     * {@code o.equals（e）}，如果这个队列包含一个或多个这样的
     * 元素。返回{@code true}当且仅当此队列包含
     * 指定的元素（或等效地，如果此队列作为
     * 通话结果）。
     *
     * @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;
        }
    }
 /**
     * 从队列中删除第i个元素。
     *
     * 通常这种方法会将元素保留在i-1，
     * 包容，不受影响。在这种情况下，它又回来了
     * 无效的。有时，为了保持堆不变，
     * 它必须将列表中的后一个元素与前一个元素交换
     *i。在这种情况下，此方法返回元素
     * 这以前是在名单的最后，现在是在一些
     * 在我前面的位置。iterator.remove使用这个事实来
     * 避免丢失遍历元素。
     */
    @SuppressWarnings("unchecked")
    private E removeAt(int i) {
        // assert i >= 0 && i < size;
        modCount++;
        int s = --size;
        if (s == i) // 删除最后一个元素
            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;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

删除最后一个元素
直接queue[i] = null;
删除中间或者根节点元素时
先调用siftDown，在进行siftUp在来做旋转

其他的一些集合方法

contains toArray 这些都比较简单，和arraylist里面基本一致，所以不在赘述了，因为不是继承abstractlist所以 没有iterator，就自己实现了个Itr
快速失败机制
Itr迭代器

  private final class Itr implements Iterator<E> {
        /**
         * 要返回的元素的索引（到队列数组中）
         * 下一个呼叫。
         */
        private int cursor = 0;

        /**
         * 最近一次调用next返回的元素的索引
         * 除非该元素来自forgetMeNot列表。
         * 如果要删除的调用删除了元素，则设置为-1。
         */
        private int lastRet = -1;

        /**
         * 从未访问部分移动的元素队列
         * 由于“unlucky”元素的缘故，堆被放入访问的部分
         * 迭代期间的删除(不幸的元素移除是
         * 我们必须参观所有的地方
         * 此列表中的元素以完成迭代。我们这样做
         * 在我们完成“正常”迭代之后。
         *
         * 我们预计大多数迭代，甚至那些涉及删除的迭代，
         * 将不需要在此字段中存储元素。
         */
        private ArrayDeque<E> forgetMeNot = null;

        /**
         * 元素，该元素由最近对下一个iff的调用返回
         * 元素是从forgetMeNot列表中提取的。
         */
        private E lastRetElt = null;

        /**
         * 迭代器认为支持
         * 队列应该有。如果违反了这个期望，迭代器
         * 已检测到并发修改。
         */
        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;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

这里涉及到了一个ArrayDeque
removeAt方法可能导致某个元素从末尾被移动到lastRet前面，这样的话，迭代器就会丢失这个元素。为了解决这个问题，迭代器把这个元素放到了一个临时ArrayDeque里面。
这样如果lastRet没有指向有效的元素，那么有可能正在遍历ArrayDeque里面的元素，此时通过lastRetElt来指向。

总结

整个PriorityQueue 利用的堆算法 利用的原理就是， 并且是最小顶堆
队列[n]的子级是队列[2n+1]和队列[2（n+1）]。
leftNo = [2n+1]
rightNo = [2（n+1）]
PriorityQueue的peek()和element操作是常数时间，add(), offer(), 无参数的remove()以及poll()方法的时间复杂度都是log(N)。