1、PriorityQueue-底层数据结构

  1. 1、PriorityQueue底层使用了数组来存储数据，因为优先级队列：一般使用堆数据结构实现，堆一般使用数组存储。
  2. 2、成员属性有:
  3.     // 默认容量
  4.     private static final int DEFAULT_INITIAL_CAPACITY = 11;
  5.     // 队列使用数组保存数据
  6.     transient Object[] queue; 
  7.     // 元素个数，即队列的大小
  8.     private int size = 0;
  9.     // 比较器，保证优先级，为空表示不指定，则是自然顺序(用元素自己默认的比较器)
  10.     private final Comparator<? super E> comparator;
  11.     // 操作次数
  12.     transient int modCount = 0; 
  13.     private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;//容量限制

2、PriorityQueue-构造函数

  2.     private static final int DEFAULT_INITIAL_CAPACITY = 11;
  4.     //默认容量11
  5.     public PriorityQueue() {
  6.         this(DEFAULT_INITIAL_CAPACITY, null);
  7.     }
  8.     //指定容量    
  9.     public PriorityQueue(int initialCapacity) {
  10.         this(initialCapacity, null);
  11.     }
  12.     //默认容量，指定比较器
  13.     public PriorityQueue(Comparator<? super E> comparator) {
  14.         this(DEFAULT_INITIAL_CAPACITY, comparator);
  15.     }
  16.     //指定容量，指定比较器，判断传入的容量是否合法，初始化存储元素的数组及比较器
  17.     public PriorityQueue(int initialCapacity, Comparator<? super E> comparator) {
  18.         if (initialCapacity < 1)
  19.             throw new IllegalArgumentException();
  20.         this.queue = new Object[initialCapacity];
  21.         this.comparator = comparator;
  22.     }
  23.     //根据传入的集合构造队列
  24.     public PriorityQueue(Collection<? extends E> c) {
  25.         if (c instanceof SortedSet<?>) {//SortedSet类型的集合
  26.             SortedSet<? extends E> ss = (SortedSet<? extends E>) c;
  27.             this.comparator = (Comparator<? super E>) ss.comparator();//取c的比较器
  28.             initElementsFromCollection(ss);//元素入队
  29.         }
  30.         else if (c instanceof PriorityQueue<?>) {//同上
  31.             PriorityQueue<? extends E> pq = (PriorityQueue<? extends E>) c;
  32.             this.comparator = (Comparator<? super E>) pq.comparator();
  33.             initFromPriorityQueue(pq);
  34.         }
  35.         else {
  36.             this.comparator = null;//自然顺序
  37.             initFromCollection(c);
  38.         }
  39.     }
  40.     @SuppressWarnings("unchecked")
  41.     public PriorityQueue(PriorityQueue<? extends E> c) {
  42.         this.comparator = (Comparator<? super E>) c.comparator();
  43.         initFromPriorityQueue(c);
  44.     }
  45.     @SuppressWarnings("unchecked")
  46.     public PriorityQueue(SortedSet<? extends E> c) {
  47.         this.comparator = (Comparator<? super E>) c.comparator();
  48.         initElementsFromCollection(c);
  49.     }
  50.     private void initFromPriorityQueue(PriorityQueue<? extends E> c) {
  51.         if (c.getClass() == PriorityQueue.class) {//说明是相同的类型，直接赋值
  52.             this.queue = c.toArray();
  53.             this.size = c.size();
  54.         } else {
  55.             initFromCollection(c);
  56.         }
  57.     }
  58.     private void initElementsFromCollection(Collection<? extends E> c) {
  59.         Object[] a = c.toArray();
  60.         if (c.getClass() != ArrayList.class)//底层是数组，进行数组拷贝
  61.             a = Arrays.copyOf(a, a.length, Object[].class);
  62.         int len = a.length;
  63.         if (len == 1 || this.comparator != null)
  64.             for (int i = 0; i < len; i++)
  65.                 if (a[i] == null)
  66.                     throw new NullPointerException();//不支持null元素
  67.         this.queue = a;
  68.         this.size = a.length;
  69.     }
  70.     private void initFromCollection(Collection<? extends E> c) {
  71.         initElementsFromCollection(c);
  72.         heapify();//堆化:从有子节点的最靠后元素开始往前，每次都调用siftDown方法来调整的过程。
  73.     }

3、PriorityQueue-扩容

  1. 1、PriorityQueue-扩容：扩容函数grow()类似于ArrayList里的grow()函数，就是再申请一个更大的数组，并将原数组的元素复制过去。
  2.     1-1、[!!!]旧容量小于64时，容量翻倍，旧容量大于等于64，容量只增加旧容量的一半。
  3. 2、源码Demo: 
  4.     private void grow(int minCapacity) {
  5.         // 旧容量
  6.         int oldCapacity = queue.length;
  8.         // 旧容量小于64时，容量翻倍，旧容量大于等于64，容量只增加旧容量的一半
  9.         int newCapacity = oldCapacity + ((oldCapacity < 64) ?
  10.                                          (oldCapacity + 2) :
  11.                                          (oldCapacity >> 1));
  12.         // 检查是否溢出
  13.         if (newCapacity - MAX_ARRAY_SIZE > 0)
  14.             newCapacity = hugeCapacity(minCapacity);
  16.         // 创建出一个新容量大小的新数组并把旧数组元素拷贝过去
  17.         queue = Arrays.copyOf(queue, newCapacity);
  18.     }
  20.     private static int hugeCapacity(int minCapacity) {
  21.         if (minCapacity < 0) // overflow
  22.             throw new OutOfMemoryError();
  23.         return (minCapacity > MAX_ARRAY_SIZE) ?
  24.             Integer.MAX_VALUE :
  25.             MAX_ARRAY_SIZE;
  26.     }

4、PriorityQueue-添加元素

  1. 1、添加元素，主要方法有： .add(E e)和.offer(E e)
  3.     //向优先队列中插入元素,在插入失败时抛出异常
  4.     public boolean add(E e) {
  5.         return offer(e);
  6.     }
  7.     //向优先队列中插入元素,在插入失败时返回false
  8.     public boolean offer(E e) {
  9.         //不允许放入null元素
  10.         if (e == null)
  11.             throw new NullPointerException();
  12.         modCount++;
  13.         int i = size;
  14.         if (i >= queue.length)
  15.             grow(i + 1); //自动扩容
  16.         size = i + 1; // 元素个数加1
  17.         if (i == 0) //队列原来为空，这是插入的第一个元素
  18.             queue[0] = e;
  19.         else
  20.             //新加入的元素可能会破坏小顶堆的性质，因此需要进行必要的调整。
  21.             siftUp(i, e); //调整堆结构，从下而上堆化
  22.         return true;
  23.     }
  25. 2、调堆结构:
  26.     //调整节点顺序/位置,因为这是一个最小堆，最小堆必须要严格按照子节点大于父亲节点的顺序做数组中存放。
  27.     //在k位置插入项x
  28.     private void siftUp(int k, E x) {
  29.         if (comparator != null)
  30.             siftUpUsingComparator(k, x);
  31.         else
  32.             siftUpComparable(k, x);
  33.     }
  35.     //有比较器,调用该方法进行节点位置调整
  36.     private void siftUpUsingComparator(int k, E x) {
  37.         while (k > 0) {
  38.             int parent = (k - 1) >>> 1;
  39.             Object e = queue[parent];
  40.             if (comparator.compare(x, (E) e) >= 0)
  41.                 break;
  42.             queue[k] = e;
  43.             k = parent;
  44.         }
  45.         queue[k] = x;
  46.     }
  48.     //没有比较器，调用该方法进行节点位置调整
  49.     private void siftUpComparable(int k, E x) {
  50.         Comparable<? super E> key = (Comparable<? super E>) x;
  51.         while (k > 0) {
  52.             int parent = (k - 1) >>> 1;    //右移一位，相当于/2，与计算公式：parentNo = (nodeNo-1)/2对应。
  53.             Object e = queue[parent];
  54.             //调用比较器的比较方法：比较可以是元素的自然顺序，也可以是依靠比较器的顺序。
  55.             //从k指定的位置开始，将x逐层与当前点的parent进行比较并交换
  56.             if (key.compareTo((E) e) >= 0) 
  57.                 break;
  58.             queue[k] = e;
  59.             k = parent;
  60.         }
  61.         queue[k] = key;
  62.     }

4-1、PriorityQueue-offer(E e)-堆化过程示意图

容器(集合)-PriorityQueue-源码分析 - 图1

5、PriorityQueue-获取元素

  1. 1、获取元素，主要方法有： .element(E e)和.peek(E e)。【获取但不删除队首元素，也就是队列中权值最小的那个元素。】
  2. 2、源码：
  3.     //当方法失败时返回null
  4.      public E peek() {
  5.         if (size == 0)
  6.             return null;
  7.         return (E) queue[0]; //根据小顶堆的性质，堆顶那个元素就是全局最小的那个；由于堆用数组表示，根据下标关系，0下标处的那个元素既是堆顶元素。所以直接返回数组0下标处的那个元素即可。
  8.     }
  10.     //当方法失败时抛出异常
  11.     public E element() {
  12.         E x = peek();
  13.         if (x != null)
  14.             return x;
  15.         else
  16.             throw new NoSuchElementException();
  17.     }

5-1、PriorityQueue-peek()-示意图

容器(集合)-PriorityQueue-源码分析 - 图2

6、PriorityQueue-删除元素

  1. 1、删除元素，涉及方法：.remove()和.poll()。【获取并删除队首元素】
  2. 2、源码：
  4.     //获取并删除队首元素,当方法失败时抛出异常
  5.      public boolean remove(Object o) {
  6.          //找到第一个满足o.equals(queue[i])元素的下标
  7.         int i = indexOf(o);
  8.         if (i == -1)
  9.             return false;
  10.         else {
  11.             removeAt(i);
  12.             return true;
  13.         }
  14.     }
  16.     //删除元素位置不同，按不同情况处理
  17.     private E removeAt(int i) {
  18.         assert i >= 0 && i < size;
  19.         modCount++;
  20.         int s = --size;
  21.         if (s == i) //1. 删除的是最后一个元素。直接删除即可，不需要调整。
  22.             queue[i] = null;
  23.         else {    //2. 删除的不是最后一个元素，从删除点开始以最后一个元素为参照调用一次siftDown()即可。
  24.             E moved = (E) queue[s];
  25.             queue[s] = null;
  26.             siftDown(i, moved);
  27.             if (queue[i] == moved) {
  28.                 siftUp(i, moved);
  29.                 if (queue[i] != moved)
  30.                     return moved;
  31.             }
  32.         }
  33.         return null;
  34.     }
  36.     //获取并删除队首元素,当方法失败时返回null
  37.     public E poll() {
  38.         if (size == 0)
  39.             return null;
  40.         int s = --size;
  41.         modCount++;
  42.         E result = (E) queue[0];//0下标处的那个元素就是最小的那个
  43.         E x = (E) queue[s];
  44.         queue[s] = null;
  45.         //由于删除操作会改变队列的结构，为维护小顶堆的性质，需要进行必要的调整。
  46.         if (s != 0)
  47.             siftDown(0, x);
  48.         return result;
  49.     }
  51.     //调用siftDown()方法对堆进行调整，最后返回原来0下标处的那个元素（也就是最小的那个元素）
  52.     private void siftDown(int k, E x) {
  53.         if (comparator != null)
  54.             siftDownUsingComparator(k, x);
  55.         else
  56.             siftDownComparable(k, x);
  57.     }
  59.     //从k指定的位置开始，将x逐层向下与当前点的左右孩子中较小的那个交换，直到x小于或等于左右孩子中的任何一个为止。
  60.     private void siftDownComparable(int k, E x) {
  61.         Comparable<? super E> key = (Comparable<? super E>)x;
  62.         // 只需要比较一半就行了，因为叶子节点占了一半的元素
  63.         int half = size >>> 1;        // loop while a non-leaf
  64.         //首先找到左右孩子中较小的那个，记录到c里，并用child记录其下标。【自上而下堆化】
  65.         while (k < half) {
  66.             //寻找子节点的位置，这里加1是因为元素从0号位置开始
  67.             int child = (k << 1) + 1; //leftNo = parentNo*2+1
  68.             //左子节点的值
  69.             Object c = queue[child];
  70.             //右子节点的位置
  71.             int right = child + 1;
  72.             if (right < size &&
  73.                 ((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
  74.                  //左右节点取其小者
  75.                 c = queue[child = right];
  76.             if (key.compareTo((E) c) <= 0)
  77.                 break;
  78.             // 如果比最小的子节点大，则交换位置
  79.             queue[k] = c;
  80.             k = child;
  81.         }
  82.         // 找到正确的位置，放入元素
  83.         queue[k] = key;
  84.     }
  86.     //从k指定的位置开始，将x逐层向下与当前点的左右孩子中较小的那个交换，直到x小于或等于左右孩子中的任何一个为止。
  87.     private void siftDownUsingComparator(int k, E x) {
  88.         int half = size >>> 1;
  89.         //首先找到左右孩子中较小的那个，记录到c里，并用child记录其下标。【自上而下堆化】
  90.         while (k < half) {
  91.             int child = (k << 1) + 1;//leftNo = parentNo*2+1
  92.             Object c = queue[child];
  93.             int right = child + 1;
  94.             if (right < size &&
  95.                 comparator.compare((E) c, (E) queue[right]) > 0)
  96.                 c = queue[child = right];
  97.             if (comparator.compare(x, (E) c) <= 0)
  98.                 break;
  99.             queue[k] = c;//然后用c取代原来的值
  100.             k = child;
  101.         }
  102.         queue[k] = x;
  103.     }

6-1、PriorityQueue-删除元素-.poll()-.siftDown()图解过程

容器(集合)-PriorityQueue-源码分析 - 图3

6-2、PriorityQueue-删除元素-.remove(Object o)-两种删除情况图解

容器(集合)-PriorityQueue-源码分析 - 图4

7、PriorityQueue-建堆过程

  1. 1、PriorityQueue的建堆过程和最大堆的建堆过程基本上一样的，从有子节点的最靠后元素开始往前，每次都调用siftDown方法来调整。这个过程也叫做heapify。
  2. 2、源码：
  4.     private void heapify() {
  5.         for (int i = (size >>> 1) - 1; i >= 0; i--)
  6.             //siftDown的过程是将一个节点和它的子节点进行比较调整，保证它比它所有的子节点都要小。这个调整的顺序是从当前节点向下，一直调整到叶节点。
  7.             siftDown(i, (E) queue[i]);
  8.     }

8、PriorityQueue-应用场景以及测试案例

  1. 1、应用场景，队列中元素，需要按照优先队列，也就是队列里面的元素遵从一定的比较规则(比较器比较)有序。
  2. 2、测试Demo：
  4.     public class PriorityQueueTest {
  5.         public static void main(String[] args) {
  6.             PriorityQueue<Integer> queue = Queues.newPriorityQueue();
  7.             test2(queue);
  8.             while (!queue.isEmpty()){
  9.                 System.out.println(queue.poll());
  10.             }
  11.         }
  13.         private static void test1(Queue queue){
  14.             queue.add(1);
  15.             queue.add(8);
  16.             queue.add(3);
  17.             queue.add(5);
  18.             queue.add(2);
  19.             queue.add(448);
  20.             queue.add(328);
  21.             queue.add(18);
  22.             queue.add(558);
  23.             queue.add(38);
  24.             queue.add(98);
  25.         }
  27.         private static void test2(Queue queue){
  28.             queue.add("a");
  29.             queue.add("v");
  30.             queue.add("d");
  31.             queue.add("s");
  32.             queue.add("z");
  33.             queue.add("da");
  34.             queue.add("dda");
  35.             queue.add("tgfa");
  36.             queue.add("yha");
  37.             queue.add("ihfa");
  38.             queue.add("mdtad");
  39.         }
  40.     }
  42.     输出结果：
  43.         1
  44.         2
  45.         3
  46.         5
  47.         8
  48.         18
  49.         38
  50.         98
  51.         328
  52.         448
  53.         558
  55.         a
  56.         d
  57.         da
  58.         dda
  59.         ihfa
  60.         mdtad
  61.         s
  62.         tgfa
  63.         v
  64.         yha
  65.         z