PriorityQueue
单端队列,队列中的元素有优先级的顺序
// 存储队列元素的数组
transient Object[] queue;
// 队列中实际元素的个数
private int size = 0;
// 比较器,用于定义队列中元素的优先级
private final Comparator<? super E> comparator;
从成员变量的定义可以看出,底层数据存储依然是数组,然而同javadoc中解释,实际的存储结构却是二叉树(大顶堆,小顶堆);
至于队列中成员的优先级使用comparator
或者成员变量本身的比较来确定
下面通过添加和删除元素来确定数据结构
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);
}
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;
}
shifDownUsingComparator
实现的就是维持小顶堆二叉树的逻辑,后面以添加为例,给一个图解
确定存储结构为小顶堆之后,再看添加元素
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;
else
siftUp(i, e);
return true;
}
// 扩容逻辑,扩容为新size的两倍,或者新增原来容量的一半
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);
}
// 二叉树重排
private void siftUp(int k, E x) {
if (comparator != null)
siftUpUsingComparator(k, x);
else
siftUpComparable(k, x);
}
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;
}
PriorityQueue
存储结构为二叉树,小顶堆