Java集合（15）——PriorityQueue源码解析

类图

官方文档

（1）优先队列PriorityQueue具有小根堆性质，该类在逻辑上是使用堆实现的，即完全二叉树；该类在存储内存时，是将其转换为数组存储的
（2）完全二叉树是指：叶节点只能出现在最下层和次下层，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树。下图显示一棵完全二叉树和一棵非完全二叉树

（3）PriorityQueue总是先输出根节点的值，然后调整树使之继续成为一棵完全二叉树，保证每次输出的根节点总是整棵树优先级最高的，要么数值最小要么数值最大

成员变量

（2）用来存储结点信息的数组的大小
（3）用来存储结点信息的数组
（4）队列数组中存储的元素个数
（5）比较器，用于制定队列中结点值大小的比较规则，因为堆在每次调整的时候都要比较结点值的大小关系，因此比较器很重要
（6）用于记录队列在结构上修改的次数，要注意该值与iterator之间的关系，否则容易抛出异常（ConcurrentModificationException异常 ）

成员方法

成员方法源码解析

1. public PriorityQueue()无参构造方法

    public PriorityQueue() {
        this(DEFAULT_INITIAL_CAPACITY, null);
    }

源码解析：

• 功能：创建一个初始容量为11(DEFAULT_INITIAL_CAPACITY)的PriorityQueue，其中队列中元素的比较方式是按照自然排序的方式进行比较
• 源码思路：
  
  • 调用该类的带有两个参数的构造方法实现创建对象

2. public PriorityQueue(int initialCapacity)方法

    public PriorityQueue(int initialCapacity) {
        this(initialCapacity, null);
    }

源码解析：

• 功能：创建一个带有初始容量的优先队列，其中队列中元素的比较方式是按照自然排序的方式进行比较
• 源码思路：
  
  • 调用该类的带有两个参数的构造方法实现创建对象

3. public PriorityQueue(Comparator<? super E> comparator)方法

    public PriorityQueue(Comparator<? super E> comparator) {
        this(DEFAULT_INITIAL_CAPACITY, comparator);
    }

源码解析：

• 功能：创建一个带有比较器的优先队列，其中队列的容量为默认的初始容量DEFAULT_INITIAL_CAPACITY（11）
• 源码思路：
  
  • 调用该类的带有两个参数的构造方法实现创建对象

4. public PriorityQueue(int initialCapacity,Comparator<? super E> comparator)方法

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

源码解析：

• 功能：创建一个带有比较器，带有自定义队列容量的优先队列
• 源码思路：
  
  • （1）首先判断自定义队列容量是否小于1，小于1时抛出异常
  • （2）给队列的数组queue创建容量为initialCapacity的内存空间
  • （3）将比较器传递给当前对象

5. public PriorityQueue(Collection<? extends E> c)方法

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

源码解析：

• 功能：创建一个优先队列，队列中包含集合c中的元素，如果集合c的类型是SortedSet或者是PriorityQueue类型，那么创建的优先队列中元素的比较方法按照集合c的比较方法进行比较，否则按照自然顺序进行比较
• 源码思路：
  
  • （1）判断如果集合c属于SortedSet类型，则将集合c强制转换为SortedSet类型，将c的比较器赋值给当前优先队列对象的比较器，然后调用initElementsFromCollection()方法，创建优先队列
  • （2）如果集合c不属于SortedSet类型，而属于PriorityQueue类型，则将集合c强制转换为PriorityQueue类型，将c的比较器赋值给当前优先队列对象的比较器，然后调用initFromPriorityQueue（）方法，创建优先队列
  • （3）如果（1）和（2）中的判断条件都不满足，则将当前优先队列的比较器设置为空，调用initFromCollection（）方法，创建优先队列

6. public PriorityQueue(PriorityQueue<? extends E> c)方法

    @SuppressWarnings("unchecked")
    public PriorityQueue(PriorityQueue<? extends E> c) {
        this.comparator = (Comparator<? super E>) c.comparator();
        initFromPriorityQueue(c);
    }

源码解析：

• 功能：创建一个优先队列，队列中包含优先队列c中的元素
• 源码思路：
  
  • （1）将c的比较器赋值给当前队列的比较器
  • （2）调用initFromPriorityQueue()方法，创建优先队列

7. public PriorityQueue(SortedSet<? extends E> c)方法

    @SuppressWarnings("unchecked")
    public PriorityQueue(SortedSet<? extends E> c) {
        this.comparator = (Comparator<? super E>) c.comparator();
        initElementsFromCollection(c);
    }

源码解析：

• 功能：创建一个优先队列，队列中包含SortedSet类型对象c中的元素
• 源码思路：
  
  • （1）将c的比较器赋值给当前对象的比较器中
  • （2）调用initElementsFromCollection方法，创建优先队列

8. private void initFromPriorityQueue(PriorityQueue<? extends E> c)方法

    private void initFromPriorityQueue(PriorityQueue<? extends E> c) {
        if (c.getClass() == PriorityQueue.class) {
            this.queue = c.toArray();
            this.size = c.size();
        } else {
            initFromCollection(c);
        }
    }

源码解析：

• 功能：这是一个子方法，实现的功能是将优先队列c中的数组和数组大小赋值给当前优先队列对象中
• 源码思路：
  
  • （1）首先判断c的类型是否是PriorityQueue类型，如果是则将优先队列c中的数组和数组大小赋值给当前优先队列对象中
  • （2）如果c的类型不是PriorityQueue类型，则调用initFromCollection()方法

9. private void initElementsFromCollection(Collection<? extends E> c)方法

    private void initElementsFromCollection(Collection<? extends E> c) {
        Object[] a = c.toArray();
        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;
    }

源码解析：

• 功能：将集合c中的数组值和数组大小传递给当前优先队列对象中
• 源码思路：
  
  • （1）首先定义个Object类型的数组a，将c中的元素转换到数组a中
  • （2）判断a集合的类型是否是Object类型的数组，如果不是，通过调用Arrays类的copyOf方法，将其转换为Object类型的数组
  • （3）定义一个整型变量len，用于存储数组a的长度
  • （4）如果数组长度为1或者迭代器不为null时，进行循环操作，循环的内容是：判断数组中是否有null元素，如果有则抛出异常，如果所有元素都不为null，则执行（5）
  • （5）将数组a的值赋值给当前优先队列的queue，将数组的长度赋值给当前优先队列的size

10. private void initFromCollection(Collection<? extends E> c)方法

    private void initFromCollection(Collection<? extends E> c) {
        initElementsFromCollection(c);
        heapify();
    }

源码解析：

• 功能：将集合c中的元素赋值给当前优先队列
• 源码思路：
  
  • （1）调用initElementsFromCollection()方法实现赋值操作
  • （2）调用heapify()方法

11. private void grow(int minCapacity)方法

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

源码解析：

• 功能：增加数组的容量
• 源码思路：
  
  • （1）定义整型变量newCapacity，其值为优先队列数组的长度
  • （2）如果长度小于64，则添加到原来的2倍，如果大于64，则增加为原来的一半
  • （3）如果新增加的数组容量大于整型的最大值-8，那么需要调用hugeCapacity()方法修改数组容量
  • （4）最后将数组和新的容量返回给当前队列数组

12. private static int hugeCapacity(int minCapacity)方法

    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

源码解析：

• 功能：按照minCapacity对数组进行扩容
• 源码思路：
  
  • （1）如果想要添加的容量值小于0，则抛出异常
  • （2）返回minCapacity大于MAX_ARRAY_SIZE值，则返回整型最大值，否则返回MAX_ARRAY_SIZE值

13. public boolean add(E e)方法

    public boolean add(E e) {
        return offer(e);
    }

源码解析：

• 功能：向优先队列中添加元素e
• 源码思路：
  
  • 调用该类的offer()方法实现该操作

14. public boolean offer(E e)方法

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

源码解析：

• 功能：向优先队列中添加元素e，添加元素的核心是siftUp()方法
• 源码思路：
  
  • （1）首先判断元素e是否为null，如果为null，则抛出异常，否则执行下述步骤
  • （2）因为向队列中插入元素，修改了队列的结构，所以modCount需要自加1
  • （3）定义变量i，用来队列的size
  • （4）如果变量i的值大于队列的数组长度，需要调用grow()方法，增加队列数组的长度，对应的size值要+1
  • （5）如果i=0，说明队列中没有元素，那么新插进来的元素就可以作为树根，否则要调用siftUp()方法来实现小根堆的调整

15. public E peek()方法

    public E peek() {
        return (size == 0) ? null : (E) queue[0];
    }

源码解析：

• 功能：获取队列中的队头元素，即小根堆的根结点值
• 源码思路：
  
  • （1）判断如果size的值等于0，说明队列中没有元素，返回null；否则返回队列的头元素

16. private int indexOf(Object o)方法

    private int indexOf(Object o) {
        if (o != null) {
            for (int i = 0; i < size; i++)
                if (o.equals(queue[i]))
                    return i;
        }
        return -1;
    }

源码解析：

• 功能：查找队列中元素值为o的结点的位置
• 源码思路：
  
  • （1）首先判断查找的元素是否为null，如果是null，因为队列中不存储null元素，因此返回-1，否则执行（2）步骤
  • （2）通过for循环进行遍历，每次遍历都使用equals方法来比较当前的元素是否与o元素相等，如果相等，则返回当前元素的位置

17. public boolean remove(Object o)方法

    public boolean remove(Object o) {
        int i = indexOf(o);
        if (i == -1)
            return false;
        else {
            removeAt(i);
            return true;
        }
    }

源码解析：

• 功能：移除队列中元素为o的结点
• 源码思路：
  
  • （1）首先根据元素o调用indexOf()方法找到元素o的位置，将该位置存储在变量i中
  • （2）判断i的值是否为-1，-1表示队列中不包含该元素，则返回false
  • （3）如果队列中包含该元素，则调用removeAt()方法，将该元素从队列中移除

18. boolean removeEq(Object o)方法

    boolean removeEq(Object o) {
        for (int i = 0; i < size; i++) {
            if (o == queue[i]) {
                removeAt(i);
                return true;
            }
        }
        return false;
    }

源码解析：

• 功能：将元素o从队列中移除
• 源码思路：
  
  • 通过for循环遍历元素，使用==运算符判断是否找到元素，找到后调用remove()方法将元素从队列中移除

19. public boolean contains(Object o)方法

    public boolean contains(Object o) {
        return indexOf(o) != -1;
    }

源码解析：

• 功能：判断队列中是否包含元素o
• 源码思路：
  
  • 调用indexOf()方法，如果有该元素，indexOf()方法会返回元素的位置
  • 判断元素位置是否为-1，如果为-1则说明不包含该元素，方法返回false，否则返回true

20. public Object[] toArray()方法

    public Object[] toArray() {
        return Arrays.copyOf(queue, size);
    }

源码解析：

• 功能：将队列的元素转换为数组
• 源码思路：
  
  • 调用Arrays.copyOf()方法，将队列中的数组和数组大小传递到方法中，返回Object类型数组

21. public <T> T[] toArray(T[] a)方法

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

源码解析：

• 功能：将队列中的元素存储在数组a中
• 源码思路：
  
  • （1）首先定义一个final int类型的变量size，获取当前队列的size
  • （2）如果将返回的数组大小小于当前队列的size大小，则直接调用Arrays类的copyOf方法将队列和队列的大小，a的类型传递进去，返回该队列对应的数组。否则执行步骤（3）
  • （3）调用System类的arraycopy方法，将queue数组从0开始赋值给数组a，赋值的数组大小为size
  • （4）如果a数组的大小大于size，说明设定的初始将返回的数组a大小太大，需要将多余的部分的第一个元素设置为null

22. public Iterator<E> iterator()方法

    public Iterator<E> iterator() {
        return new Itr();
    }

源码解析：

• 功能：创建优先队列的迭代器

23. public int size()方法

   public int size() {
        return size;
    }

源码解析：

• 功能：返回队列的size元素个数

24. public void clear()方法

    public void clear() {
        modCount++;
        for (int i = 0; i < size; i++)
            queue[i] = null;
        size = 0;
    }

源码解析：

• 功能：清除队列中的所有元素
• 源码思路：
  
  • （1）因为清除操作是对队列的结构性修改，因此需要让modCount自加1
  • （2）使用for循环遍历队列，每次循环都将循环到的元素值置为null
  • （3）最后将size的值变为0

25. public E poll()方法

    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）首先判断队列中是否有元素，如果有元素，则返回null
  • （2）定义变量s，其值等于队列的size-1，同时将队列的size值-1
  • （3）定义变量result，其值等于堆的根结点值，定义变量x，其值等于堆的最后一个元素的值
  • （4）将堆的最后一个元素值置为null，因为要删除根结点，所以满足堆的定义，最后一个元素一定为null
  • （5）如果队列的最后一个元素不是堆的第一个元素，就需要将堆的最后一个元素按照小根堆的规则找到它的新位置，因此调用siftDown()方法进行调整

26. private E removeAt(int i)方法

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

源码解析：

• 功能：移除队列中位置为i的元素
• 源码思路：
  
  • （1）因为移除操作是对队列的结构上的修改，所以需要modCount+1
  • （2）定义整型变量s，其值等于size-1,同时将队列的size值-1
  • （3）如果要删除的元素是队列的最后一个元素，则直接将最后一个元素置为null
  • （4）否则定义变量moved，用来存储队列中的最后一个元素
  • （5）因为要移除一个元素，因此队列的最后一个元素要移动保证小根堆的性质，所以最后一个元素一定变为null，移动最后一个元素的规则是调用siftDown(i, moved)方法
  -

27. private void siftUp(int k, E x)方法

    private void siftUp(int k, E x) {
        if (comparator != null)
            siftUpUsingComparator(k, x);
        else
            siftUpComparable(k, x);
    }

源码解析：

• 功能： 在k位置插入元素x
• 源码思路：
  
  • （1）首先判断迭代器是否为null，如果不为空调用siftUpUsingComparator(k, x)方法，保证队列是小根堆
  • （2）如果迭代器尾null，调用siftUpComparable(k, x)方法

28. private void siftUpComparable(int k, E x)方法

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

源码解析：

• 功能：向队列中位置为k的地方插入元素x
• 源码思路：
  
  • （1）首先获取元素x的比较器，将其放在Comparable类型的key变量中
  • （2）循环，循环条件k>0。定义变量parent，其值等于位置为k的元素的父节点的位置
  • （3）定义变量e，其值为 位置为k的元素的父节点的位置的变量
  • （4）调用构造器判断当前将插入的元素与插入位置的父节点的值大小，如果大于父节点的值，则满足小根堆，直接跳出循环，将插入的元素x插入到位置k；否则，执行步骤（5）
  • （5）将位置为k的元素值变为其父节点的值，将其父节点的值变为插入元素x的值

下面示例：
当前队列中有如下元素[1, 2, 8, 9, 6]

元素在逻辑上的存储方式如上图，现在想要再插入元素4，即如果执行add(4)方法，会出现的结果是

该过程如果用siftUpComparable()方法来讲解的话，过程如下：

1. 首先k=5， parent = （5-1）/2 = 2，e = 10， 因为比较的结果是queue[parent] > queue[k]，所以将8放在位置5，k = 2;
2. 当前k=2，parent = 0，e = 1，因为比较的结果是queue[parent]< queue[k]，所以不执行if里面的语句，而执行queue[0] = 1，k = 0
3. 因为 k =0，退出循环体
4. 最后执行queue[2] = 4

29. private void siftUpUsingComparator(int k, E x)方法

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

源码解析：

• 功能：向队列中位置为k的地方插入元素x，与上一个方法的不同之处就是这个方法提供了自己的比较器，因此比较结点值大小的时候使用提供的比较器比较

30. private void siftDown(int k, E x)方法

    private void siftDown(int k, E x) {
        if (comparator != null)
            siftDownUsingComparator(k, x);
        else
            siftDownComparable(k, x);
    }

源码解析：

• 功能：从堆的第一个元素往下比较，如果比左右孩子节点的最小值小则与最小值交换，交换后继续向下比较，否则停止比较

31. private void siftDownComparable(int k, E x)方法

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

源码解析：