java集合：PriorityQueue
一 序：
之前在看shardingjdbc的OrderByStreamResultSetMerger的时候，用了PriorityQueue。
来看看对应的实现.
先补充下相关概念：
队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。
队列是一种特征为FIFO的数据结构，每次从队列中取出的是最早加入队列中的元素。但是，许多应用需要另一种队列，每次从队列中取出的应是具有最高优先权的元素，这种队列就是优先级队列(Priority Queue)，也称为优先权队列。
一个基于优先级堆的*优先级队列。优先级队列的元素按照其自然顺序进行排序，或者根据构造队列时提供的 Comparator 进行排序，具体取决于所使用的构造方法。优先级队列不允许使用 null 元素。依靠自然顺序的优先级队列还不允许插入不可比较的对象.
二 源码
2.1 成员变量
private static final long serialVersionUID = -7720805057305804111L;
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默认容量是11.这一点跟hashmap那种2的N次不同。
关于堆补充下说明：
堆是一种经过排序的完全二叉树，其中任一非终端节点的数据值均不大于（或不小于）其左孩子和右孩子节点的值。
根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最小者的堆称为小根堆。
根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大者，称为大根堆。
对于PriorityQueue，它容量没有界限，且默认排序是自然排序，队头元素是最小元素，故我们可以拿来作为小根堆使用。对于大根堆，就要借助于comparator比较器，来实现大根堆。不看实现只看根堆名字容易误解：以为又是二叉树呢，上面显示是数组实现的。
2.2 构造方法
//默认长度，无比较器
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);
}
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];// PriorityQueue是在构造函数调用阶段就已经申请了底层数组
this.comparator = comparator;
}2.3 入队
add(E e) 和 offer(E e) 方法都是向PriorityQueue中加入一个元素，其中add（）其实调用了offer（）方法如下：
public boolean add(E e) {
return offer(e);
}public boolean offer(E e) {
if (e == null)
throw new NullPointerException();
//如果压入的元素为null 抛出异常
int i = size;
if (i >= queue.length)
grow(i + 1);
//如果数组的大小不够扩充
size = i + 1;
if (i == 0)
queue[0] = e;
//如果只有一个元素之间放在堆顶
else
siftUp(i, e);
//否则调用siftUp函数从下往上调整堆。
return true;
}1：安全性检查，不运行插入null元素
2：容量检查，如果容量不够，则扩容。扩容原则：如果当前基层数组较小，则扩容时，每次扩展一倍。之后每次扩容时，每次扩展0.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 code
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
queue = Arrays.copyOf(queue, newCapacity);
}3. 如果当前队列为空，则直接插入到queue[0]位置，不需要调整。否则，将元素直接放到最后位置，然后调整，不断上浮。主要逻辑在siftUp实现.下面看看具体实现。
private void siftUp(int k, E x) {
if (comparator != null)
//使用插入元素的实现的比较器调整节点位置
siftUpUsingComparator(k, x);
else
//使用默认的比较器（按照自然排序规则）调整节点的位置
siftUpComparable(k, x);
}
//使用默认的比较器调整元素的位置
private void siftUpComparable(int k, E x) {
Comparable<? super E> key = (Comparable<? super E>) x;
while (k > 0) {
//父节点位置：如果父亲节点是N,则两个孩子节点2*N+1,2(N+1),反推孩子节点编号k,则父亲节点为(k - 1) >>> 1
int parent = (k - 1) >>> 1;
//保存父节点的值
Object e = queue[parent];
//使用compareTo方法，如果要插入的元素小于父节点的位置则交换两个节点的位置
if (key.compareTo((E) e) >= 0)
break;
queue[k] = e;
k = parent;
}
queue[k] = key;
}
//调用实现的比较器进行元素位置的调整，总的过程和上面一致，就是比较的方法不同
private void siftUpUsingComparator(int k, E x) {
while (k > 0) {
int parent = (k - 1) >>> 1;
Object e = queue[parent];
//这里是compare方法
if (comparator.compare(x, (E) e) >= 0)
break;
queue[k] = e;
k = parent;
}
queue[k] = x;
}上面的代码还是比较简明的，就是当前元素与父节点不断比较如果比父节点小就交换然后继续向上比较，否则停止比较的过程。
这改变我之前的 第一印象，不是树实现的，数组的顺序也不是有序的。这里要理解对应关系，把数据结构中复杂的树形元素放在简单的数组中。就是父节点与子节点在数组中的位置：对于父节点i，左孩子节点的下标left(i)=2*i，右孩子节点right(i) = 2*i+1。
举个例子：
public static void main(String[] args) {
Queue queue = new PriorityQueue();
for(int i=9;i>=0;i--)
{
queue.offer(i);
System.out.print(queue.toString() );
System.out.println(queue.peek());
}
}输出：
[9]9
[8, 9]8
[7, 9, 8]7
[6, 7, 8, 9]6
[5, 6, 8, 9, 7]5
[4, 6, 5, 9, 7, 8]4
[3, 6, 4, 9, 7, 8, 5]3
[2, 3, 4, 6, 7, 8, 5, 9]2
[1, 2, 4, 3, 7, 8, 5, 9, 6]1
[0, 1, 4, 3, 2, 8, 5, 9, 6, 7]0
可以看见每次插入都需要调整。为了更好地演示，我从网上找了个动图：
2.4 出队
poll 方法每次从 PriorityQueue 的头部删除一个节点，也就是从小顶堆的堆顶删除一个节点。
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;
}跟offer相反。
1.容量检查
2.size标志减一，同时保存堆顶元素。
3.将最后一个元暂时提到堆顶位置，然后将堆顶元素调整，下移。主要实现在siftDown
//在位置k插入元素x，为了保持最小堆的性质会不断调整节点位置
private void siftDown(int k, E x) {
if (comparator != null)
//使用插入元素的实现的比较器调整节点位置
siftDownUsingComparator(k, x);
else
//使用默认的比较器（按照自然排序规则）调整节点的位置
siftDownComparable(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-leaf
//如果不是叶子节点则一直循环
while (k < half) {
//得到k位置节点左孩子节点，假设左孩子比右孩子更小
int child = (k << 1) + 1; // assume left child is least
//保存左孩子节点值
Object c = queue[child];
//右孩子节点的位置
int right = child + 1;
//把左右孩子中的较小值保存在变量c中
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;
}
//循环结束，k是叶子节点
queue[k] = key;
}堆中每次删除只能删除头节点。也就是数组中的第一个节点。 将最后一个节点替代头节点然后进行调整。
siftDown方法就是从堆的第一个元素往下比较，如果比左右孩子节点的最小值小则与最小值交换，交换后继续向下比较，否则停止比较。
再看看另一个删除方法remove(), remove(Object o) 来删除堆中的与给定对象相同的最先出现的对象
public boolean remove(Object o) {
int i = indexOf(o);
//先在堆中找到o的位置
if (i == -1)
return false;
//如果不存在则返回false。
else {
removeAt(i);
//否则删除数组中第i个位置的值，调整堆。
return true;
}
}private E removeAt(int i) {
assert i >= 0 && i < size;
modCount++;
//s是队列的队头，对应到数组中就是最后一个元素
int s = --size;
//如果要移除的位置是最后一个位置，则把最后一个元素设为null
if (s == i) // removed last element
queue[i] = null;
else {
//保存待删除的节点元素
E moved = (E) queue[s];
queue[s] = null;
//先把最后一个元素和i位置的元素交换，之后执行下调方法
siftDown(i, moved);
//如果执行下调方法后位置没变，说明该元素是该子树的最小元素，需要执行上调方//法,保持最小堆的性质
if (queue[i] == moved) {//位置没变
siftUp(i, moved); //执行上调方法
if (queue[i] != moved)//如果上调后i位置发生改变则返回该元素
return moved;
}
}
return null;
}看个例子：
或者是在队列:[0, 1, 4, 3, 2, 8, 5, 9, 6, 7]
调用poll去掉根节点，remove（5）
输出：[1, 2, 4, 3, 7, 8, 5, 9, 6]
[1, 2, 4, 3, 7, 8, 6, 9]
3 其他
清除元素
public void clear() {
modCount++;
for (int i = 0; i < size; i++)
queue[i] = null;
size = 0;
}为了防止内存泄漏，不只是把size置0.
堆化函数
如果在构造PriorityQueue时，使用一个非priorityqueue集合初始queue，则策略是先将集合中的元素拷贝到底层的数组中，然后调用堆化函数调整元素顺序，使满足堆的性质。
private void heapify() {
for (int i = (size >>> 1) - 1; i >= 0; i--)
siftDown(i, (E) queue[i]);
}总结：
priorityqueue是*队列
时间复杂度：remove()方法和add()方法时间复杂度为O(logn)，remove(Object obj)和contains()方法需要O(n)时间复杂度，取队头则需要O(1)时间
在初始化阶段会执行建堆函数，最终建立的是最小堆，每次出队和入队操作不能保证队列元素的有序性，只能保证队头元素和新插入元素的有序性，如果需要有序输出队列中的元素，则只要调用Arrays.sort()方法即可
PriorityQueue是非同步的，要实现同步需要调用java.util.concurrent包下的PriorityBlockingQueue类来实现同步
在队列中不允许使用null元素
还有个比较器实现大根堆的没测试。
参考：
https://blog.csdn.net/u013309870/article/details/71189189
https://blog.csdn.net/u011116672/article/details/50997622
上一篇： 使用BigDecimal进行精确运算(实现加减乘除运算)
下一篇： 堆（Heap）的实现