PriorityQueue 原理与应用

灰太狼 2022-06-05 00:48 260阅读 0赞

# 深入理解 PriorityQueue 优先队列 #

最近在使用DelayQueue时候，发现其底层是基于PriorityQueue实现的，接着这个机会深入分析一下优先队列的实现原理，方便以后在最适合的地方应用。

> 本文主要的结构分为以下几点：  
> 1）PriorityQueue的类继承关系  
> 2）PriorityQueue的核心数据结构以及数据结构实现原理  
> 3）PriorityQueue的核心方法以及实现原理  
> 4）PriorityQueue应用场景以及测试案例

# PriorityQueue的类继承关系 #

优先队列的类继承关系相对简单，主要是主要是实现了两个接口：Collection和Queue，类继承图如下：

![这里写图片描述][SouthEast]

# PriorityQueue的核心数据结构（最小堆） #

## 核心属性 ##

首先我们先来看看PriorityQueue的核心成员属性：

transient Object[] queue;// 队列使用数组保存数据
    private int size = 0;//队列的大小
    /** 队列里面的元素使用的比较器，如果不指定，就是用元素自己默认的比较器。PriorityQueue就是通过这个比较器来实现排序 */
    private final Comparator<? super E> comparator;

从成员变量我们可以知道以下几点：

1.  优先级队列使用数据保存数据
2.  PriorityQueue里面元素的有序性是通过一个比较器实现的

## 核心构造器 ##

我们再看看构造器，这里只列出几个核心的构造器：

public PriorityQueue() {
        this(DEFAULT_INITIAL_CAPACITY, null);
    }
    
    public PriorityQueue(int initialCapacity) {
        this(initialCapacity, null);
    }
    
    public PriorityQueue(int initialCapacity,
                         Comparator<? super E> comparator) {
        // Note: This restriction of at least one is not actually needed,
        // but continues for 1.5 compatibility
        if (initialCapacity < 1)
            throw new IllegalArgumentException();
        this.queue = new Object[initialCapacity];
        this.comparator = comparator;
    }

从几个核心的构造器我们可以知道：

1.  优先级队列可以指定初始化容量，如果不指定有默认初始化容量(超过会自动扩容)。
2.  如果构造器不指定比较器comparator，那么就会使用队列里面元素默认的构造器比较。

## 底层数据结构 ##

从目前已知的成员属性和构造器还得不出其具体的存储数据结构，看过里面的offer()、take()等函数源码之后，就知道 ***PriorityQueue是使用最小堆实现的优先队列的存储。*** 也就是说是 使用数组实现最小堆存储。

下面以一张图来解释存储结构：

以一个优先队列：3、5、7、9、10、11、12、13、15、20. 为例，以下是存储结构

![这里写图片描述][SouthEast 1]

上图中我们给每个元素按照层序遍历的方式进行了编号，如果你足够细心，会发现父节点和子节点的编号是有联系的，更确切的说父子节点的编号之间有如下关系：

leftNo = parentNo*2+1
    
    rightNo = parentNo*2+2
    
    parentNo = (nodeNo-1)/2

通过上述三个公式，可以轻易计算出某个节点的父节点以及子节点的下标。这也就是为什么可以直接用数组来存储堆的原因。

PriorityQueue的peek()和element操作是常数时间，add(), offer(), 无参数的remove()以及poll()方法的时间复杂度都是log(N)。

# PriorityQueue的核心方法以及实现原理 #

PriorityQueue首先是一个队列，下面我就队列的特性，分析一下PriorityQueue作为队列提供的核心函数实现原理：

public boolean offer(E e)
    
    public E poll()
    
    public E peek()

## offer() 或则 add() ##

add(E e)和offer(E e)的语义相同，都是向优先队列中插入元素，只是Queue接口规定二者对插入失败时的处理不同，前者在插入失败时抛出异常，后则则会返回false。对于PriorityQueue这两个方法其实没什么差别。

下图以插入元素4为例：

![这里写图片描述][SouthEast 2]

新加入的元素可能会破坏小顶堆的性质，因此需要进行必要的调整。

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

上述代码中，扩容函数grow()类似于ArrayList里的grow()函数，就是再申请一个更大的数组，并将原数组的元素复制过去，这里不再赘述。需要注意的是siftUp(int k, E x)方法，该方法会直接调用siftUpComparable(k, x)方法，用于插入元素x，并基于元素的比较器维持堆的特性。

private void siftUpComparable(int k, E x) {
        Comparable<? super E> key = (Comparable<? super E>) x;
        while (k > 0) {
            int parent = (k - 1) >>> 1;//parentNo = (nodeNo-1)/2
            Object e = queue[parent];
            if (key.compareTo((E) e) >= 0)//调用比较器的比较方法
                break;
            queue[k] = e;
            k = parent;
        }
        queue[k] = key;
    }

新加入的元素x可能会破坏小顶堆的性质，因此需要进行调整。调整的过程为：从k指定的位置开始，将x逐层与当前点的parent进行比较并交换，直到满足x >= queue\[parent\]为止。注意这里的比较可以是元素的自然顺序，也可以是依靠比较器的顺序。

## peek() ##

这个函数就比较简单了，返回优先级队列的最小的元素，由于PriorityQueue底层基于最小堆，最小堆又采用数组存储，所以堆顶元素即数组的第一个元素。

public E peek() {
        if (size == 0)
            return null;
        return (E) queue[0];//0下标处的那个元素就是最小的那个
    }

## remove()和poll() ##

remove()和poll()方法的语义也完全相同，都是获取并删除队首元素，区别是当方法失败时前者抛出异常，后者返回null。由于删除操作会改变队列的结构，为维护小顶堆的性质，需要进行必要的调整。

下图以删除最小元素3 为例：

![这里写图片描述][SouthEast 3]

源码如下：

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

上述代码首先记录0下标处的元素，并用最后一个元素替换0下标位置的元素，之后调用siftDown()方法对堆进行调整，最后返回原来0下标处的那个元素（也就是最小的那个元素）。重点是siftDown(int k, E x)方法，siftDown()会直接调用siftDownComparable()方法，该方法的作用是从k指定的位置开始，将x逐层向下与当前点的左右孩子中较小的那个交换，直到x小于或等于左右孩子中的任何一个为止。

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) {
            //首先找到左右孩子中较小的那个，记录到c里，并用child记录其下标
            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;//然后用c取代原来的值
            k = child;
        }
        queue[k] = key;
    }

# PriorityQueue应用场景以及测试案例 #

PriorityQueue的应用场景很容易想像，何谓优先队列，也就是队列里面的元素遵从一定的比较规则(比较器比较)有序。

比如DelayQueue底层用到PriorityQueue实现，也就是PriorityQueue里面保存的元素是按照超过过期时间由小到大排序的有序队列。

下面给出以下PriorityQueue实际测试demo

public class PriorityQueueTest { 
        public static void main(String[] args) {
            PriorityQueue<Integer> queue = Queues.newPriorityQueue();
            test2(queue);
            while (!queue.isEmpty()){
                System.out.println(queue.poll());
            }
        }
    
        private static void test1(Queue queue){
            queue.add(1);
            queue.add(8);
            queue.add(3);
            queue.add(5);
            queue.add(2);
            queue.add(448);
            queue.add(328);
            queue.add(18);
            queue.add(558);
            queue.add(38);
            queue.add(98);
        }
    
        private static void test2(Queue queue){
            queue.add("a");
            queue.add("v");
            queue.add("d");
            queue.add("s");
            queue.add("z");
            queue.add("da");
            queue.add("dda");
            queue.add("tgfa");
            queue.add("yha");
            queue.add("ihfa");
            queue.add("mdtad");
        }
    }

运行test1()输出结果是：

1
    2
    3
    5
    8
    18
    38
    98
    328
    448
    558

运行test2()输出结果是：

a
    d
    da
    dda
    ihfa
    mdtad
    s
    tgfa
    v
    yha
    z

[SouthEast]: /images/20220605/94cbdf3d416c4cf9a463e6c975771446.png
[SouthEast 1]: /images/20220605/684463c42c724af3bc6b9c33fa9cd116.png
[SouthEast 2]: /images/20220605/6ef2c7a9ddcf4758a6f9c86e8316de2d.png
[SouthEast 3]: /images/20220605/8f9da3ffbc8b4822b90706ab952dcf55.png