吃透Java集合系列七：PriorityQueue

本文主要是介绍吃透Java集合系列七：PriorityQueue，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一：PriorityQueue实现方式

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

二：源码分析

重要变量以及构造函数

• 根据堆的特性，存储结构肯定是数组。
• 支持不同优先级，肯定有比较器，也就是说支持自定义排序和顺序排序。
• PriorityQueue的构造函数有很多，主要参数是容量和比较器。

public class PriorityQueue<E> extends AbstractQueue<E>implements java.io.Serializable {
//默认容量11
private static final int DEFAULT_INITIAL_CAPACITY = 11;
//堆的存储结构，存储元素
transient Object[] queue;
//当前存储的元素数量
private int size = 0;
//自定义比较器
private final Comparator<? super E> comparator;
public PriorityQueue(int initialCapacity,Comparator<? super E> comparator) {if (initialCapacity < 1)throw new IllegalArgumentException();this.queue = new Object[initialCapacity];this.comparator = comparator;}

扩容机制

每次扩容，当前容量小于64时就扩容为原来的2倍+2，当前容量大于等于64时扩容为原来的1.5倍。

	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 codeif (newCapacity - MAX_ARRAY_SIZE > 0)newCapacity = hugeCapacity(minCapacity);queue = Arrays.copyOf(queue, newCapacity);}private static int hugeCapacity(int minCapacity) {if (minCapacity < 0) // overflowthrow new OutOfMemoryError();return (minCapacity > MAX_ARRAY_SIZE) ?Integer.MAX_VALUE :MAX_ARRAY_SIZE;}

add()和offer()

add(E e)和offer(E e)的语义相同，都是向优先队列中插入元素，只是Queue接口规定二者对插入失败时的处理不同，前者在插入失败时抛出异常，后则则会返回false。对于PriorityQueue这两个方法其实没什么差别。

	public boolean add(E e) {return offer(e);}public boolean offer(E e) {if (e == null)//不允许放入null元素throw new NullPointerException();modCount++;int i = size;if (i >= queue.length)grow(i + 1);//扩容size = i + 1;if (i == 0)//队列原来为空，这是插入的第一个元素queue[0] = e;elsesiftUp(i, e);//调整return true;}private void siftUp(int k, E x) {if (comparator != null)siftUpUsingComparator(k, x);elsesiftUpComparable(k, x);}private void siftUpUsingComparator(int k, E x) {while (k > 0) {int parent = (k - 1) >>> 1;//parentNo = (nodeNo-1)/2Object e = queue[parent];if (comparator.compare(x, (E) e) >= 0) //调用比较器的比较方法,break;				//如果当前值大于等于父节点则跳出循环queue[k] = e;//如果当前值小于父节点，则父节点与当前值交换位置k = parent;//当前节点位置调整为原父节点位置，进入下一次循环}queue[k] = 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;}

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

element()和peek()

element()和peek()的语义完全相同，都是获取但不删除队首元素，也就是队列中权值最小的那个元素，二者唯一的区别是当方法失败时前者抛出异常，后者返回null。根据小顶堆的性质，堆顶那个元素就是全局最小的那个；由于堆用数组表示，根据下标关系，0下标处的那个元素既是堆顶元素。所以直接返回数组0下标处的那个元素即可。

	public E element() {E x = peek();if (x != null)return x;elsethrow new NoSuchElementException();}public E peek() {return (size == 0) ? null : (E) queue[0];}

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

	public E poll() {if (size == 0)return null;int s = --size;modCount++;E result = (E) queue[0];//0下标处的那个元素就是最小的那个E x = (E) queue[s];queue[s] = null;if (s != 0)siftDown(0, x);return result;}private void siftDown(int k, E x) {if (comparator != null)siftDownUsingComparator(k, x);elsesiftDownComparable(k, x);}private void siftDownUsingComparator(int k, E x) {int half = size >>> 1;while (k < half) {//首先找到左右孩子中较小的那个，记录到c里，并用child记录其下标int child = (k << 1) + 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;//然后用c取代原来的值k = child;}queue[k] = x;}private void siftDownComparable(int k, E x) {Comparable<? super E> key = (Comparable<? super E>)x;int half = size >>> 1;        // loop while a non-leafwhile (k < half) {int child = (k << 1) + 1; // assume left child is leastObject 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;}

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

remove(Object o)

remove(Object o)方法用于删除队列中跟o相等的某一个元素（如果有多个相等，只删除一个），该方法不是Queue接口内的方法，而是Collection接口的方法。由于删除操作会改变队列结构，所以要进行调整；又由于删除元素的位置可能是任意的，所以调整过程比其它函数稍加繁琐。具体来说，remove(Object o)可以分为2种情况：1. 删除的是最后一个元素。直接删除即可，不需要调整。2. 删除的不是最后一个元素，从删除点开始以最后一个元素为参照调用一次siftDown()即可。此处不再赘述。

	public boolean remove(Object o) {int i = indexOf(o);if (i == -1)return false;else {removeAt(i);return true;}}private E removeAt(int i) {// assert i >= 0 && i < size;modCount++;int s = --size;if (s == i) // removed last elementqueue[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;}

此文用到的图片均来源于此作者，感谢！

这篇关于吃透Java集合系列七：PriorityQueue的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---