优先级队列

>>强大,10k+点赞的 SpringBoot 后台管理系统竟然出了详细教程!

队列与栈两种数据结构是老生常谈的问题了,其中队列是先进先出(FIFO),栈是先进后出(FILO),明白这两个特性,就很简易理解了。但是有一种特殊的队列也是我们常用的数据结构——优先级队列。

优先队列的作用是能保证每次取出的元素都是队列中权值最小(大)的,Java中PriorityQueue实现了Queue接口,不允许放入null元素;其通过堆实现,具体说是通过完全二叉树(complete binary tree)实现的小顶堆(任意一个非叶子节点的权值,都不大于其左右子节点的权值),也就意味着可以通过数组来作为PriorityQueue的底层实现。如下图所式:

优先级队列

面着重两个方法说明,添加元素与移除元素。

添加元素时,通过siftUp(int k, E x);方法维持特性。

 1public boolean offer(E e) {
2    if (e == null)//不允许放入null元素
3        throw new NullPointerException();
4    modCount++;
5    int i = size;
6    if (i >= queue.length)
7        grow(i + 1);//自动扩容
8    size = i + 1;
9    if (i == 0)//队列原来为空,这是插入的第一个元素
10        queue[0] = e;
11    else
12        siftUp(i, e);//调整
13    return true;
14}
15
16private void siftUp(int k, E x) {
17    while (k > 0) {
18        int parent = (k - 1) >>> 1;//parentNo = (nodeNo-1)/2
19        Object e = queue[parent];
20        if (comparator.compare(x, (E) e) >= 0)//调用比较器的比较方法
21            break;
22        queue[k] = e;
23        k = parent;
24    }
25    queue[k] = x;
26}

k为数组最大下标值。 看下图所示:

优先级队列

 1//代码运行过程
2-> x = 4;
3-> k = 10;
4-> parent = (k-1)/2 = 4.5 === 4;
5-> e = 9;
6-> compare(49) = -1 < 0;
7-> queue[10] = 9;
8-> k = 4;
9-> parent = (k-1)/2 = 1.5 === 1;
10-> e = 5;
11-> compare(4,5) = -1 < 0;
12-> queue[4] = 5;
13-> k=1;
14-> parent = (k - 1) / 2 = 0 / 2 === 0;
15-> e = 3;
16-> compare(43) = 1 > 0;
17//跳出while循环
18-> queue[1] = x => queue[1] = 4;

至此,添加元素的过程结束。
再看一下poll过程,poll过程是通过siftDown(int k , E e);来维持特性。

 1public E poll() {
2    if (size == 0)
3        return null;
4    int s = --size;
5    modCount++;
6    E result = (E) queue[0];//0下标处的那个元素就是最小的那个
7    E x = (E) queue[s];
8    queue[s] = null;
9    if (s != 0)
10        siftDown(0, x);//调整
11    return result;
12}
13
14private void siftDown(int k, E x) {
15    int half = size >>> 1;
16    while (k < half) {
17        //首先找到左右孩子中较小的那个,记录到c里,并用child记录其下标
18        int child = (k << 1) + 1;//leftNo = parentNo*2+1
19        Object c = queue[child];
20        int right = child + 1;
21        if (right < size &&
22            comparator.compare((E) c, (E) queue[right]) > 0)
23            c = queue[child = right];
24        if (comparator.compare(x, (E) c) <= 0)
25            break;
26        queue[k] = c;//然后用c取代原来的值
27        k = child;
28    }
29    queue[k] = x;
30}

k的初始值为0,x为最后一个元素。
过程如图所示:

优先级队列

 1//代码运行过程
2-> k = 0;
3-> x = 9;
4-> half = 10 / 2 = 5;
5-> child = 0 + 1 = 1;
6-> c = 4;
7-> right = child + 1 = 2;
8// 2<10 && compare(4, 10)<0第一个判断不成立
9-> compare(94) > 0;
10-> queue[0] = 4;
11-> k = 1;
12-> child = 2 * 1 + 1 = 3;
13-> c = 7;
14-> right = 4;
15-> 4 < 10 && compare(75)>0
16-> child = 4;
17-> c = 5;
18-> compare(95)>0
19-> queue[1] = 5;
20-> k = 4;
21-> child = 2 * 4 + 1 = 9;
22-> c = 12;
23-> right = 10;
24// 10<10第一个判断不成立
25-> compare(912)<0;
26//跳出while循环
27-> queue[4] = 9

至此,poll操作过程结束。


原文始发于微信公众号(铭轩):优先级队列