Java PriorityQueue优先队列详解(源码+图文步骤解析)

文章目录

1、概述

PriorityQueue 称为优先队列,也是一种特殊的有序队列。为什么特殊呢?

因为其内部使用 Object[] 数组来存储数据,整个数组从0 ~ 最后一个并不是有序排放的,但是出队的时候数据又是从小到大有序的。

来看个例子:

public class PriorityQueueTest {
    public static void main(String[] args) {
        PriorityQueue queue = new PriorityQueue();
        Random random = new Random();
        final int count = 7;
        System.out.print("入队开始:");
        for (int i = 0; i < count; i++){
            int number = random.nextInt(100);
            System.out.print(number + ",");
            queue.offer(number);
        }
        System.out.println();
        System.out.print("队列数组:");
        for (Object o : queue.toArray()) {
            System.out.print(o + ",");
        }
        System.out.println();
        System.out.print("出队开始:");
        for (int i = 0; i < count; i++) {
            Object number = queue.poll();
            System.out.print(number + ",");
        }
    }
}

输出结果如下,如上面所说,数组的内容不是按顺序的,但是出队是从小到大有序的:

入队开始:86,13,66,49,82,37,87,
队列数组:13,49,37,86,82,66,87,
出队开始:13,37,49,66,82,86,87,

2、入队分析

offer 源码:

    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;
    }

offer 流程图:
Java PriorityQueue优先队列详解(源码+图文步骤解析)
上面最后一步,特殊的入队逻辑 具体是怎样的,咱继续分析一下。

先上源码:

	//k:数组第一个空位的索引值,例如:当前已经填充了2个元素,再次执行到这里k就是2
	//x:准备入队的对象
    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;
    }

这段代码的大致逻辑是:

  • 查到当前入队对象(x)的父对象(e),这里的父对象不是上一个元素,也是类似树结构的父对象,下面会讲到
  • 如果 x >= e,则将 x 放到数组下标位置 k,执行结束
  • 如果 x < e,把 e 放到数组下标位置 k,同时把原下标赋给 k,继续执行第一步

这里用到移位运算法,顺便讲解一下

int parent = (k - 1) >>> 1:获取当前元素的父级,>>> 1 表示将二进制值右移1位,左边补0

举几个例子:

十进制0,对应二进制0000,右移1位仍然是0000,结果是0
十进制1,对应二进制0001,右移1位变成0000,结果是0
十进制2,对应二进制0010,右移1位变成0001,结果是1
十进制3,对应二进制0011,右移1位变成0001,结果是1
十进制4,对应二进制0100,右移1位变成0010,结果是2
十进制5,对应二进制0101,右移1位变成0010,结果是2

用一个流程图表示就是这样:
Java PriorityQueue优先队列详解(源码+图文步骤解析)
分解步骤,就以上面的入队顺序为例子(86,13,66,49,82,37,87):

第1个对象,x = 86,直接放到数组第0位

Java PriorityQueue优先队列详解(源码+图文步骤解析)

第2个对象,x = 13

  • k = 1,parent = 0,因为 13 < 86,所以执行queue[1] = 86
  • 然后执行 k = parent,也就是 k = 0,所以执行 queue[0] = 13
    Java PriorityQueue优先队列详解(源码+图文步骤解析)

第3个对象,x = 66

  • k=2,parent=0,因为 66 > 13,所以直接放在 k 位置上
    Java PriorityQueue优先队列详解(源码+图文步骤解析)

第4个对象,x = 49

  • k=3,parent=1,因为 49 < 86,所以 86 要往下移
    Java PriorityQueue优先队列详解(源码+图文步骤解析)
  • 因为此时 49 > 13,所以不需要继续移位

第5个对象,x = 82

  • k=4,parent=1,因为 82 > 49,所以直接赋值
    Java PriorityQueue优先队列详解(源码+图文步骤解析)

第6个对象,x = 37

  • k=5,parent=2,因为 37 < 66,所以 66 需要下移
    Java PriorityQueue优先队列详解(源码+图文步骤解析)
  • 因为37 > 13,所以不需要继续移位

第7个对象 x = 87

  • k=6,parent=2,因为 87 > 37,所以直接赋值
    Java PriorityQueue优先队列详解(源码+图文步骤解析)
    此时数组顺序变成了:13,49,37,86,82,66,87,跟我们前面测试结果一致

结论

  • 数组的顺序是无序排列
  • 从根节点到叶子节点的分支,内部是有序的

3、出队分析

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;
    }

poll 流程图:
Java PriorityQueue优先队列详解(源码+图文步骤解析)

如图所示:

  • 如果当前数组的数据超过1个,会先执行 siftDown 方法
  • 方法最后一定是返回 result (数组第1个元素)。因此我们可以大胆猜测,siftDown 执行完毕后,数组的第1个元素一定是最小的

出队拆解:

初始状态

Java PriorityQueue优先队列详解(源码+图文步骤解析)

第1次出队

前面我们说过,执行 siftDown 之后,队列顶部一定是最小的元素。第1次出队的数据是13,之后最小的元素一定是13的两个子节点之一。因此,siftDown 的第1步就是找到左右两个子节点,把比较小的元素移动到根节点。

如下代码所示:

	//k:此处值是 0
	//x:当前数组最后一个元素
    private void siftDownComparable(int k, E x) {
        Comparable<? super E> key = (Comparable<? super E>)x;
        //size:数组最后一个元素的下标值
        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。因此,c记录的是最小的数据
                c = queue[child = right];
            if (key.compareTo((E) c) <= 0)
                break;
            //把最小的数据(变量c)往上移
            queue[k] = c;
            k = child;
        }
        queue[k] = key;
    }

代码中while第一次循环结束后,数组结构如下。37 < 49,所以37被移到根节点。
Java PriorityQueue优先队列详解(源码+图文步骤解析)

但是,下标2仍然记录着37,所以下一步就是把 k 设置成下标2,然后重复执行前面的步骤:获取37的左右节点,把最小的往上移。如下图所示:
Java PriorityQueue优先队列详解(源码+图文步骤解析)
第三次while循环时,k 变成 5,已经没有下级节点了,所以循环结束。

最后执行 queue[k] = key ,也就是把最后一个元素设置成左节点

Java PriorityQueue优先队列详解(源码+图文步骤解析)

第2次出队、第3次出队等等,原理都一样的,这里就不逐一说明了

4、总结

  • PriorityQueue执行入队和出队时,都会进行排序比较。因此入队的对象必须实现 Comparable 接口,或者在实例化PriorityQueue对象的时候定义 Comparator 方法(构造函数传参)
  • PriorityQueue 是非线程安全的,多线程环境必须使用 PriorityBlockingQueue
  • PriorityQueue 入队时间复杂度是O(log),因为要维护树的层级关系
  • PriorityQueue 出队时间复杂度是O(log),原因同上
上一篇:PriorityBlockingQueue 分析


下一篇:Codeforces Round #102 (Div. 1) A. Help Farmer 暴力分解