PriorityQueue 源码分析
PriorityQueue 优先队列, 采用小顶堆排序实现; 本文主要针对常用的操作 add, poll, peek 进行分析
添加元素 - add
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;
// Double size if small; else grow by 50%
// 若当前长度 < 64 则扩容一倍,反正扩容 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);
}
复制代码
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) {
// 获取父节点索引 >>> 等效于 (k - 1) / 2
int parent = (k - 1) >>> 1;
Object e = queue[parent];
// 待添加元素大于父节点元素时终止上浮
if (key.compareTo((E) e) >= 0)
break;
// 将父节点元素下移
queue[k] = e;
// k 指向父节点索引
k = parent;
}
queue[k] = key;
}
复制代码
从 siftUpComparable 方法可以看出, 优先队列采用的是小顶堆实现。
获取元素并删除 - poll
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;
}
复制代码
private void siftDown(int k, E x) {
if (comparator != null)
siftDownUsingComparator(k, x);
else
siftDownComparable(k, x);
}
@SuppressWarnings("unchecked")
private void siftDownComparable(int k, E x) {
Comparable<? super E> key = (Comparable<? super E>)x;
// >>> 等效于 size / 2
int half = size >>> 1; // loop while a non-leaf
// k < half 即对非叶子节点进行下沉操作
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 指向子节点索引处
k = child;
}
queue[k] = key;
}
复制代码
获取元素不删除 - peek
public E peek() {
// 返回根节点元素
return (size == 0) ? null : (E) queue[0];
}
复制代码
从 add,poll 方法的实现我们可以看出, 对于优先队列来说,每次在添加元素时采用上浮
,删除元素时采用下移
的操作来保证根节点(也即数组的首节点)元素为最值,这样每次从队列获取元素时也就是我们业务上优先级最高的元素。
关于堆排序的实现可参考 堆排序