java.util.PriorityQueue源码学习笔记

1
transient Object[] queue; // non-private to simplify nested class access

解读源码的注释:

基于数组实现的,节点 n 的 子节点的 index 为:

如果没有指定排序规则,那么按照自然排序规则排序,通过数组的形式表达了平衡二叉树的结构。默认是小顶堆的实现。

1560149252015

图解 PriorityQueue 小顶堆的实现

这个类是非线程安全的1

主要看 addofferpeekremovepoll这几个方法。

add、offer

add 中直接调用offer,所以我们直接看offer。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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;
}
  1. 如果插入的元素是空,那么抛出空指针
  2. 判断是否需要扩容
  3. 如果是第一个参数直接入列。
  4. 否则执行方法 siftUp,入参 i 数组的长度,e 需要入队的数据
1
2
3
4
5
6
private void siftUp(int k, E x) {
if (comparator != null)
siftUpUsingComparator(k, x);
else
siftUpComparable(k, x);
}
  1. 我们以未指定排序规则为例进入方法 siftUpComparable
1
2
3
4
5
6
7
8
9
10
11
12
13
@SuppressWarnings("unchecked")
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;
}

例:如果我们以此通过add加入 3、5、2,那么此方法的执行解析为

  1. 3 -> queue[3]
  2. 5 -> siftUpComparable(k,x),k = 1 x = 5
    • parent = (1 -1) / 2 = 0
    • e = 3
    • key > 3 break;queue[3,5]
  3. 2 -> siftUpComparable(k,x),k = 2 x = 2
    • parent = (2-1)/2 = 0
    • e = 3
    • key < 3
    • queue[2] = 3 ,k = 0;queue[3,5,3];
    • queue[0] = 2;queue[2,5,3]

至此完成添加 siftUpUsingComparator 同样的步骤。

peek

1
2
3
4
@SuppressWarnings("unchecked")
public E peek() {
return (size == 0) ? null : (E) queue[0];
}

poll

1
2
3
4
5
6
7
8
9
10
11
12
13
@SuppressWarnings("unchecked")
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;
}

返回 rote 数据,并移除。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
@SuppressWarnings("unchecked")
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;
}

又遇到了这种我思维跟不上的逻辑了。

查阅资料对于这种平衡二叉树,index 小于 half size 的都不是叶子节点。这里利用了这个特点。

例:queue[2,5,3]

  1. queue[2,3],half = 1,k = 0,x = 5
  2. 移除的 index 不是叶子节点,那么获取其左右子节点进行比较。
    默认取左节点为基准值,如果右节点存在且比作节点小,那么以右节点为基准值。
    如果入参 x 比基准值小,那么退出循环。
    否则将 k 处的值设置为基准值 c,k = 左右节点较小的index。继续循环。
    queue[3,3]
  3. 找到了 x 应该位置 k ,queue[3,5]。
1. use the thread-safe {@linkjava.util.concurrent.PriorityBlockingQueue} class

留言

⬆︎TOP