深入学习Java之PriorityQueue
前言
在前面一个小节中我们深入学习了LinkedList，并且从LinkedList的结构图中得知，LinkedList实现了Queue接口，今天这一小节，主要来学习Queue接口的另外一个实现，PriorityQueue，也就是优先队列，所谓的优先队列，就是在队列中根据某一个特征值自动进行排序，优先队列分为两种，最大优先队列和最小优先队列，优先队列的一个最大特性就是，当插入元素或者删除元素的时候，队列会自动进行调整，保证队首元素一定是优先权最大/最小。正是由于优先队列的这种特性，优先队列可以被用在很多地方，比如作业调度，进程调度等。
堆与堆排序
在深入学习优先队列之前，我们必须先来学习堆这一种数据结构，因为优先队列的内部正是采用堆这一种数据结构来实现的，并且，在进行操行的时候，时刻进行堆的维护，所以接下来我们先来学习堆以及堆的操作，然后顺便学习一个优秀的排序算法，堆排序，最后再深入学习优先队列
比较常用的一种堆结构是二叉堆，二叉堆的实质是一个二叉树，只不过这个二叉树有点特殊，每一个父子节点都是其子孙节点中的最大值，称之为最大堆，反之则称之为最小堆，下面采用最大堆来演示，最小堆原理相同，二叉堆一般采用数组来进行维护即可，并且，由于其本身的特性，可以得出结论，堆的左孩子索引为 i * 2， 右孩子索引为 i * 2 + 1,其中i为父亲节点的索引
接下来我们来看一下一个简单的二叉堆
二叉堆示例
从图中可以看到，每一个父子节点的值都比其子孙节点大，也就是说，根节点的值是整个堆中的值最大的一个，这就是最大堆名字的由来了
建立二叉堆的方法非常简单，根据二叉堆的特性，只需要对每个元素执行调整即可，调整的具体过程为，从后往前调整，如果发现一个元素的值比其孩子节点(左右孩子)的值小，则跟其进行交换，并且递归其发生交换的孩子，继续进行判断，交换，直至到达第一个元素，不过这里有一个可以提高效率的地方，由于叶子节点没有孩子，所以叶子节点是不需要进行交换的，具体的为，从元素个数/2开始即可，具体原因可自行学习
接下来我们来看下二叉堆的具体实现
class Heap{
private int[] data;
private int heapSize;
public Heap(int[] data, int heapSize) {
this.data = data;
this.heapSize = heapSize;
buildHeap();
}
// 建立二叉堆
private void buildHeap(){
// 从索引为堆大小/2 开始，调整元素的位置
for (int i = heapSize/2; i >= 1; i--){
heap(i);
}
}
// 建立二叉堆的具体实现
private void heap(int i){
int left = i << 1; // 左孩子索引
int right = left + 1; // 右孩子索引
int max = i;
// 如果左孩子的值比父亲的值大，则记录下左孩子索引
if (left < heapSize && data[left] > data[i]){
max = left;
}
// 如果右孩子的值比当前的最大值大，则记录下其索引
if (right < heapSize && data[right] > data[max]){
max = right;
}
// 如果孩子的值比父亲大，则进行交换
// 否则，则结束，表明已经是最大堆了
if (max != i){
int tmp = data[i];
data[i] = data[max];
data[max] = tmp;
// 递归发生交换的孩子节点
heap(max);
}
}
}
从上面可以看到，建立二叉堆是比较简单的，接下来我们来学习堆的一个应用，堆排序，堆排序是根据堆的这种特性而出现的一种排序算法，算法的流程为，首先建立二叉堆，然后每次交换第一个元素(也就是当前的最大值)与最后一个元素，调整堆，将堆的大小-1，重复上面的操作，直至堆大小为1，具体代码如下所示
// 堆排序
public void sort(){
// 建立堆
buildHeap();
while (heapSize >= 2){
// 将第一个元素与最后一个元素交换
int tmp = data[heapSize];
data[heapSize] = data[1];
data[1] = tmp;
// 堆大小-1
heapSize --;
// 从根节点调整堆，使其重新成为最大堆
heap(1);
}
}
优先队列源码剖析
首先来看下PriorityQueue的结构
PriorityQueue结构
从上图中可以看到，PriorityQueue继承自AbstractQueue，不过由于AbstractQueue中没有新增其他的方法，所以这里不打算进行展开，同时，由于其他的接口/抽象类我们在前面两个小节中均已经学习过了，所以这里就不进行展开了，直接来学习PriorityQueue的源码
首先是构造方法
// 无参构造器，默认大小为11
public PriorityQueue() {
// DEFAULT_INITIAL_CAPACITY = 11;
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];
this.comparator = comparator;
}
// 使用容器中的数据来构造优先队列
// 其中的SortedSet将在后面学习
// 从这里可以看到，如果建立的元素已经是有序的，也就是已经提供了比较器，则直接使用
// 如果不是，则按照默认的方式进行堆的建立
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);
}
}
// 使用另一个优先队列来构造
public PriorityQueue(PriorityQueue<? extends E> c) {
this.comparator = (Comparator<? super E>) c.comparator();
initFromPriorityQueue(c);
}
// 使用SortedSet来构造
public PriorityQueue(SortedSet<? extends E> c) {
this.comparator = (Comparator<? super E>) c.comparator();
initElementsFromCollection(c);
}
// 从优先队列构造
private void initFromPriorityQueue(PriorityQueue<? extends E> c) {
if (c.getClass() == PriorityQueue.class) {
this.queue = c.toArray();
this.size = c.size();
} else {
initFromCollection(c);
}
}
// 从容器中构造，并且建立堆
private void initFromCollection(Collection<? extends E> c) {
initElementsFromCollection(c);
heapify();
}
// 从容器中构造
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;
}
堆的建立与调整
// 建立堆
private void heapify() {
// 从非叶子节点进行调整
for (int i = (size >>> 1) - 1; i >= 0; i--)
siftDown(i, (E) queue[i]);
}
// 如果提供了比较器，则使用比较器进行堆调整
// 否则，使用默认的比较器进行堆调整
private void siftDown(int k, E x) {
if (comparator != null)
siftDownUsingComparator(k, x);
else
siftDownComparable(k, x);
}
// 使用比较器进行堆调整，可以看到，实现方式跟上面的调整方式基本一样
private void siftDownUsingComparator(int k, E x) {
int half = size >>> 1;
// 从上往下开始调整
while (k < half) {
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;
k = child;
}
queue[k] = x;
}
// 如果没有提供比较器，则使用元素默认的构造器
// 这也就意味着传入的元素必须是实现了Comparable接口
// 并且已经实现compareTo方法
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;
}
插入元素
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);
size = i + 1;
// 如果队列中只有一个元素，则直接放入队首
if (i == 0)
queue[0] = e;
else // 否则，将其插入最后一个位置，并且进行堆的调整
siftUp(i, e);
return true;
}
// 动态增长
private void grow(int minCapacity) {
int oldCapacity = queue.length;
// 如果容量小于64，则增长一倍，否则，增长1/2
int newCapacity = oldCapacity + ((oldCapacity < 64) ?
(oldCapacity + 2) :
(oldCapacity >> 1));
// 检查是否整数溢出
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
queue = Arrays.copyOf(queue, newCapacity);
}
// 检查是否溢出
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
// 根据有无提供比较器选择不同的比较方法
private void siftUp(int k, E x) {
if (comparator != null)
siftUpUsingComparator(k, x);
else
siftUpComparable(k, x);
}
// 从这里可以看到，调整的方法为从位置k开始，查找其
// 父节点的值，如果父节点的值比所要插入的值大，则进行交换，并且递归父节点
// 也就是从二叉树树中"往上调整"
// 否则，则不进行交换(最小堆嘛)
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;
}
// 同上，只是这里使用默认的比较器
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;
}
获得元素的索引
private int indexOf(Object o) {
if (o != null) {
for (int i = 0; i < size; i++)
if (o.equals(queue[i]))
return i;
}
return -1;
}
删除元素
public boolean remove(Object o) {
int i = indexOf(o);
if (i == -1)
return false;
else {
removeAt(i);
return true;
}
}
// 如果有相等的元素，则删除
boolean removeEq(Object o) {
for (int i = 0; i < size; i++) {
if (o == queue[i]) {
removeAt(i);
return true;
}
}
return false;
}
// 删除指定位置的元素
private E removeAt(int i) {
modCount++;
int s = --size;
if (s == i) // 删除最后一个元素
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;
}
// 删除元素，默认为第一个元素，也就是根元素
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;
}
总结
本小节我们主要学习了堆以及堆的应用，堆排序，然后深入学习了优先队列，从优先队列的源码中可以看到，优先队列的本质其实就是一个最小堆，如果要使用最大优先队列，则需要传入自定义的比较器，在优先队列中，不需要存在空元素，并且要求传入优先队列中的元素必须是实现了Comparable接口
