基于优先堆实现的无限的优先队列。队列里的元素根据它们自然的顺序或者构造函数传入的Comparator排序。PriorityQueue不允许null元素,依赖于自然顺序的优先队列也不允许无法比较的对象。
- 基于最小堆:队列的头是符合指定顺序的最小的元素,如果多个元素都是最小值,头是他们其中一个。
- 优先队列是无限的,但是有一个内部容量来控制队列上用来存储元素的数组的大小。它总是至少比size大,加入元素时自动增长。
- 非线程安全:多线程操作,使用
java.util.concurrent.PriorityBlockingQueue
代替。Important variables
1
2
3
4
5private static final int DEFAULT_INITIAL_CAPACITY = 11;
transient Object[] queue;
private int size = 0;
// null表示使用自然顺序
private final Comparator<? super E> comparator;
PriorityQueue 使用数组来存储二叉堆,如图所示数组存储二叉树有如下性质: L=2*P+1
R=2*P+2
P=(L-1)/2=(R-2)/2=int((R-2)/2)=(Node-1)/2
得到以下性质之后,后面代码中都用到。
Main Methods
grow()
1
2
3
4
5
6
7
8
9
10private void grow(int minCapacity) {
int oldCapacity = queue.length;
// 如果<64,翻倍;否则增加50%;
int newCapacity = oldCapacity + ((oldCapacity < 64) ? (oldCapacity + 2) :(oldCapacity >> 1));
// 检查是否超过最大SIZE:Integer.MAX_VALUE - 8
if (newCapacity - MAX_ARRAY_SIZE > 0)
// 允许再扩大到 Integer.MAX_VALUE
newCapacity = hugeCapacity(minCapacity);
queue = Arrays.copyOf(queue, newCapacity);
}siftUpUsingComparator()
在队列末尾加入元素,不断地同父节点进行比较,如果违反父节点小于任意子节点
的规则就和父节点交换,直到满足就停止。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15private void siftUpUsingComparator(int k, E x) {
while (k > 0) {
// 和父节点比较
int parent = (k - 1) >>> 1;
Object e = queue[parent];
// x大于等于父节点,停止
if (comparator.compare(x, (E) e) >= 0)
break;
// 将父节点放下来
queue[k] = e;
// 从父节点的位置继续网上搜索
k = parent;
}
queue[k] = x;
}shifrDownUsingComparator()
从某个位置移除原有元素后,为了收缩空间,将队列尾部的元素放到移除的位置。然后一直同子节点比较,如果违背父节点小于任意子节点
的规则,就和子节点进行交换,直到满足就停止。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18private 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;
}add()/offer()
两者基本相同,前者调用后者实现。加入元素之前确认空间,然后调用shiftUp 也就是 siftUpUsingComparator 实现元素插入并保持优先队列的特性。1
2
3
4
5
6
7
8
9
10
11
12public boolean offer(E e) {
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;
}peak()
1
2
3public E peek() {
return (size == 0) ? null : (E) queue[0];
}获取但不删除,由于再加入或者删除元素时就进行调整以维护优先队列特性,因此堆顶元素就是优先级最高的。
remove()/pool()
获取并删除,remove(Object) 表示删除队列中与equal(o)
的对象, removeEq(Object o) 表示删除队列中与==o
(同一个对象,更严格)的对象,不过两者在定位到对象后最终都通过 removeAt(i)来移除并保持队列特性;1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19private E removeAt(int i) {
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;
}pool() 是移除堆顶元素,移除之后的恢复相对简单:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15public 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;
}
Summary
- PriorityQueue的
peek()
和element
操作是常数时间,add()
,offer()
, 无参数的remove()
以及poll()
方法的时间复杂度都是*log(N)*。 - 后两张图片来自网上,侵权请联系删除。
赏
使用支付宝打赏
使用微信打赏
若你觉得我的文章对你有帮助,欢迎点击上方按钮对我打赏
扫描二维码,分享此文章