PriorityQueue源码分析

1. 基本介绍

优先队列的作用是能保证每次取出的元素都是队列中权值最小的，元素大小的评判可以通过元素本身的自然顺序（natural ordering），也可以通过构造时传入的比较器

2. 使用方法

在线api

public class Test9 { public static void main(String[] args) { int[] a = {45,36,18,53,72,30,48,93,15,35}; //2，通过比较器排序，实现最大堆 PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(new Comparator<Integer>() { @Override public int compare(Integer o1, Integer o2) { /**以下是对比较器升序、降序的理解. *(1) 写成return o1.compareTo(o2) 或者 return o1-o2表示升序 *(2) 写成return o2.compareTo(o1) 或者return o2-o1表示降序 */ return o2.compareTo(o1); } }) ; for(int i=0;i<a.length;i++) { maxHeap.offer(a[i]); } while(!maxHeap.isEmpty()) { System.out.print(maxHeap.poll()+" "); } System.out.println(); //输出（降序）：93 72 53 48 45 36 35 30 18 15 } }

3. 二叉堆

二叉堆之 Java的实现 二叉堆是完全二元树或者是近似完全二元树，按照数据的排列方式可以分为两种：最大堆和最小堆。 ① 最大堆：父结点的键值总是大于或等于任何一个子节点的键值； ② 最小堆：父结点的键值总是小于或等于任何一个子节点的键值 二叉堆一般都通过"数组"来实现，下面是数组实现的最大堆和最小堆的示意图 基本操作 二叉堆通常使用数组来实现（实际上可以用ArrayList，因为底层就是数组），数组实现的二叉堆，从根节点往下一层一层在数组依次摆放，父节点和子节点的位置存在一定的关系

假设"第一个元素"在数组中的索引为 0 的话，则父节点和子节点的位置关系如下：

① 索引为i的左孩子的索引是 (2*i+1);

② 索引为i的右孩子的索引是 (2*i+2);

③ 索引为i的父结点的索引是 floor((i-1)/2);

插入 当向最大堆中添加数据时：先将数据加入到最大堆的最后，然后尽可能把这个元素往上挪，直到挪不动为止！ 例子：在最大堆[90,80,70,60,40,30,20,10,50]中添加85 代码实现：

private int[] values = new int[16] ; private int size; /** * 上浮 * @return */ private int fixUp() { int j = size -1 ; //最后一个元素的下标 int f ; //父节点的下标 while((f = ((j -1) /2)) >= 0) { //通过父节点的下标 if(values[f] <= values[j]) break; //父节点的值小于子节点的值，则打适合的位置。 int temp = values[f] ; values[f] = values[j]; values[j] = temp ; j = f ; } return f; } /** * 添加一个元素在最小堆中上 * @return */ public int push(int item) { if(size >= values.length) Arrays.copyOf(values, size << 1) ; values[size++] = item ; return fixUp(); }

删除 先删除该数据，然后用最大堆中最后一个的元素插入这个空位；接着，把这个“空位”尽量往上挪，直到剩余的数据变成一个最大堆 例子：从最大堆[90,85,70,60,80,30,20,10,50,40]中删除90 例子：从最大堆[90,85,70,60,80,30,20,10,50,40]中删除60 代码实现

/** * 移除并获取一个堆顶元素 * @return 堆顶元素 */ public int poll() { if(size <= 0) throw new IllegalStateException("不存在元素"); int value = values[0]; values[0] = values[--size] ; //将最后一个元素提到堆顶 values[size] = 0 ; //清空最后一个的数据 fixDown(); //下沉操作 return value; } /** * 下沉 * @return 下沉到适合位置的index */ private int fixDown() { int f = 0 ; //父节点的index int k ; //较小者子节点的index while((k = (f << 1) + 1) < size) { //至少存在左子节点 if(k < size - 1) { //存在右子节点 if (values[k] > values[k + 1]) k++; //左右子节点进行比较。 } if(values[f] <= values[k]) break; //父节点小于较小者子节点，则找到合适的位置，退出循环 int temp = values[f] ; values[f] = values[k]; values[k] = temp ; f = k ; } return f; }

4. 继承关系

Java中PriorityQueue实现了Queue接口，不允许放入null元素，其通过堆实现，具体说是通过完全二叉树（complete binary tree）实现的小顶堆（任意一个非叶子节点的权值，都不大于其左右子节点的权值），也就意味着可以通过数组来作为PriorityQueue的底层实现

5. 源码分析

5.1 成员变量

public class PriorityQueue<E> extends AbstractQueue<E> implements java.io.Serializable { 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 * <i>structurally modified</i>. See AbstractList for gory details. */ transient int modCount = 0; // non-private to simplify nested class access

通过对成员变量的分析可以知道下面几点信息

1⃣️ 底层是一个Object数组 2⃣️ 优先级排序比较是通过成员变量Comparator比较器实现的 Comparator比较器

5.2 构造函数

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

5.3 add()/offer()

add(E e)和offer(E e)的语义相同，都是向优先队列中插入元素，add()方法就是调用了offer()方法 不能插入null，@throws NullPointerException if the specified element is null

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

① 不能插入null，@throws NullPointerException if the specified element is null

② 会改变 modCount++，也就是说会有fast-fail

③ 由于底层是数组实现的，所以插入会存在数组容量不够而进行扩容的操作

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

④ 新加入的元素x可能会破坏小顶堆的性质，因此需要进行调整。调整的过程为：从k指定的位置开始，将x逐层与当前点的parent进行比较并交换，直到满足x >= queue[parent]为止。注意这里的比较可以是元素的自然顺序，也可以是依靠比较器的顺序。

//siftUp() private void siftUp(int k, E x) { while (k > 0) { int parent = (k - 1) >>> 1;//parentNo = (nodeNo-1)/2 Object e = queue[parent]; if (comparator.compare(x, (E) e) >= 0)//调用比较器的比较方法 break; queue[k] = e; k = parent; } queue[k] = x; }

5.4 peak

获取但不删除队首元素，也就是队列中权值最小的那个元素；根据小顶堆的性质，堆顶那个元素就是全局最小的那个；由于堆用数组表示，根据下标关系，0下标处的那个元素既是堆顶元素。所以直接返回数组0下标处的那个元素即可。

//peek() public E peek() { if (size == 0) return null; return (E) queue[0];//0下标处的那个元素就是最小的那个 }

5.5 删除poll

public E poll() { final Object[] es; final E result;//0下标处的那个元素就是最小的那个 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; if ((cmp = comparator) == null) siftDownComparable(0, x, es, n); else siftDownUsingComparator(0, x, es, n, cmp); } } return result; }

上述代码首先记录0下标处的元素，并用最后一个元素替换0下标位置的元素，之后调用siftDown()方法对堆进行调整，最后返回原来0下标处的那个元素（也就是最小的那个元素）。重点是siftDown(int k, E x)方法，该方法的作用是从k指定的位置开始，将x逐层向下与当前点的左右孩子中较小的那个交换，直到x小于或等于左右孩子中的任何一个为止

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

5.6 迭代器

这里只是关注迭代器的next()方法

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

可见是对数组进行迭代，所以并不会按照优先级的顺序返回