数据结构之优先级队列

封面画师：ツチヤ     封面ID：78361237

本文参考视频：小马哥教育(SEEMYGO) 2019年 恋上数据结构与算法（第一季）

源码仓库：mofan212/data-structure-and-algorithm (github.com)

辅助学习网址：数据结构和算法动态可视化

1. 优先级队列

1.1 接口设计

优先级队列（Priority Queue）， 也是一个队列，因此也提供以下接口：

int size(); // 元素的数量
boolean isEmpty(); // 是否为空
void clear(); // 清空队列
void enQueue(E element); // 入队
E deQueue(); // 出队
E front(); // 获取队列的头元素

优先级队列和普通的队列一样，有队头、队尾的概念，元素也是按照“从队尾入队、从队头出队”的方式进出队列。

普通队列是 FIFO 原则，即： 先进先出。

优先级队列则是按照 优先级高低 进行 出队 ，比如将 优先级最高 的元素作为 队头 优先出队。

1.2 应用场景

1、在实际环境中，医院的夜间门诊可以看成一个优先级队列：

• 队列元素是病人，优先级是病情的严重情况、挂号时间。

2、在计算机中，操作系统的多任务调度可以看成一个优先级队列：

• 队列元素是任务，优先级是任务的类型。

1.3 思路整理

优先级队列也是一个队列，因此可以继续沿用以前编写的队列的代码，直接将其拷贝作为优先级队列的源码？

但是这又出现了问题，优先级队列之所以加个优先级三个字，必定得体现优先级，直接沿用以前的代码肯定是无法体现优先级的，那该怎么办？

思考一下优先级的含义，然后自己手写？

还记得前一篇文章 二叉堆 中的内容吗？那里面实现了一个二叉堆，这个二叉堆默认是最大堆，回忆一下最大堆的概念。

所谓最大堆，就是 任意节点的值一定不小于其子节点 。这就没了？😒

这只是最浅显的理解，最大堆还有一个特点，那就是： 最大堆的根节点的值一定是整个堆中最大的 。

嘿嘿，是不是看出什么猫腻了？😉

对头，可以使用 最大堆 来实现优先级队列。这样的话，对于优先级队列来说，出队就相当于是删除最大堆的堆顶元素，删除后，堆会进行下滤，使得堆顶元素的值一直都是整个堆中最大的。这样，就可以保证按照优先级的顺序出队了。

为了体现优先级队列中的优先级，在使用最大堆实现优先级队列时，可以将比较器 Comparator 作为优先级队列构造方法的入参，使得用户可以自定义优先级。当用户使用优先级队列时，既可以自定义一个比较器也可以使存储的数据实现 Comparable 接口，以达到自定义优先级。

1.4 代码实现

明确使用最大堆来实现优先级队列，那么这实现就很简单了。👊

新建一个名为 PriorityQueue 类，将最大堆的实现类作为 PriorityQueue 的一个成员变量即可：

/**
 * @author 默烦
 * @date 2020/8/6
 */
public class PriorityQueue<E> {
    // 使用二叉堆实现优先级队列
    private BinaryHeap<E> heap;

    public PriorityQueue (Comparator<E> comparator){
        heap = new BinaryHeap<>(comparator);
    }

    public PriorityQueue() {
        this(null);
    }

    public int size(){
        return heap.size();
    }

    public boolean isEmpty(){
        return heap.isEmpty();
    }

    public void clear(){
        heap.clear();
    }

    public void enQueue(E element){
        heap.add(element);
    }

    public E deQueue(){
        return heap.remove();
    }

    public E front(){
        return heap.get();
    }
}

新建一个实体类 Person，为测试优先级队列做准备：

public class Person implements Comparable<Person> {
    private String name;
    private int boneBreak;

    public Person(String name, int boneBreak) {
        this.name = name;
        this.boneBreak = boneBreak;
    }

    @Override
    public String toString() {
        return "Person{" +
                "name='" + name + '\'' +
                ", boneBreak=" + boneBreak +
                '}';
    }

    @Override
    public int compareTo(Person person) {
        // boneBreak 越大，优先级越高
        return this.boneBreak - person.boneBreak;
    }
}

测试代码：

/**
 * @author 默烦
 * @date 2020/8/6
 */
public class Main {
    public static void main(String[] args) {
        PriorityQueue<Person> queue = new PriorityQueue<>();
        queue.enQueue(new Person("Jack",2));
        queue.enQueue(new Person("Rose",10));
        queue.enQueue(new Person("Jake",5));
        queue.enQueue(new Person("James",15));
        while (!queue.isEmpty()) {
            System.out.println(queue.deQueue());
        }
    }
}

运行的测试结果为：

打印出来的结果符合预期。🎉

2. 源码阅读

在 JDK 中也提供了优先级队列的实现，它位于 java.util 包中，名字也叫作 PriorityQueue。

根据这个类提供的公共方法可以发现，它提供了 offer() 、 peek() 、 poll() 等一系列和操作队列相关的方法，显然 JDK 中的优先级队列也是一个队列。

JDK 中的优先级队列也提供了比较器，其中有这样一个成员变量：

private final Comparator<? super E> comparator;

基于此，这个类也有多个构造方法，这里就不一一举例了。

在这个类中，还有这样一个成员变量：

transient Object[] queue;

从这可知 JDK 中的优先级队列也是用数组实现的。

那么 JDK 中的优先级队列的优先级到底是怎么体现的呢？也是用的二叉堆吗？

PriorityQueue 中可以找到入队方法 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;
}

有一个东西是不是很熟悉，就是siftUp()，表示上滤，到此可以确定 JDK 中的优先级队列也是采用二叉堆来实现的。

查看 siftUp() 方法的具体实现：

private void siftUp(int k, E x) {
    if (comparator != null)
        siftUpUsingComparator(k, x);
    else
        siftUpComparable(k, x);
}

好像和我们编写的上滤方法不一样？

其实并不是，这只是将比较的方式分开了，换句话说，将比较器 Comparator 的比较和比较接口 Comparable 的比较分开了，而我们是将它们糅合在了一起。

JDK 中的 siftUp() 上滤方法，将比较进行如下拆分：

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

@SuppressWarnings("unchecked")
private void siftUpUsingComparator(int k, E x) {
    while (k > 0) {
        int parent = (k - 1) >>> 1;
        Object e = queue[parent];
        if (comparator.compare(x, (E) e) >= 0)
            break;
        queue[k] = e;
        k = parent;
    }
    queue[k] = x;
}

siftUpComparable() 方法和 siftUpUsingComparator() 方法基本一样，只是比较略有不同，一个使用 Comparable 接口的 compareTo() 方法，另一个使用比较器 Comparator 的 compare() 方法。

在我们自己编写时，抽取出公共代码，将它们放在一个抽象类 AbstractHeap 中，在这个类中，自定义的比较方法也在其中（具体操作可以参考上一篇文章 二叉堆 ）：

protected int compare(E e1, E e2) {
    return comparator != null ? comparator.compare(e1, e2)
            : ((Comparable<E>) e1).compareTo(e2);
}

JDK 中上滤的实现和我们自定义的上滤实现大同小异。

再看看出队方法 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;
}

和入队方法一样，里面也有一个熟悉的方法，即下滤方法 siftDown()。查看其源码，会发现和上滤类似，也是将两种比较情况分开了，因此不再赘述。

仔细研究 JDK 中的上滤或下滤方法，甚至可以发现 JDK 和采取了和我们一样的优化方式。比如对于上滤方法来说，JDK 并不是挨着一个个交换节点，而是和我们一样： 将新添加节点备份，确定最终位置后才摆放上去 。

自定义的上滤方法：

private void siftUp(int index) {
        E e = elements[index];
        while (index > 0) { // 索引位置节点有父节点时
            int pIndex = (index - 1) >> 1; // 获取父节点索引
            E p = elements[pIndex];
            if (compare(e, p) <= 0) break;

            // 将父元素存储在 index 位置
            elements[index] = elements[pIndex];
            // 重新赋值 index
            index = pIndex;
        }
        elements[index] = e;
    }

JDK 中的上滤方法：

private void siftUp(int k, E x) {
    if (comparator != null)
        siftUpUsingComparator(k, x);
    else
        siftUpComparable(k, x);
}

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

// 省略另外一个

继续看看 JDK 中的其他方法，还可以发现一个熟悉的方法 heapify()，用于实现批量建堆或者说堆化：

private void heapify() {
    for (int i = (size >>> 1) - 1; i >= 0; i--)
        siftDown(i, (E) queue[i]);
}

JDK 采取的也是 自下而上的下滤 进行批量建堆。

至于 自上而下的上滤 和 自下而上的下滤 之间的区别可以前往上一篇文章 二叉堆 中查看，有十分通俗介绍和对比。

最后一个问题，JDK 中优先级队列的采用的二叉堆是最大堆还是最小堆呢？

先上一段 PriorityQueue 源码中进行比较的代码：

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

我们自定义的上滤方法：

private void siftUp(int index) {
        E e = elements[index];
        while (index > 0) { // 索引位置节点有父节点时
            int pIndex = (index - 1) >> 1; // 获取父节点索引
            E p = elements[pIndex];
            if (compare(e, p) <= 0) break;

            // 将父元素存储在 index 位置
            elements[index] = elements[pIndex];
            // 重新赋值 index
            index = pIndex;
        }
        elements[index] = e;
    }

看出来了吧，JDK 采用的比较判断与我们的相反，JDK 使用 key.compareTo((E) e) >= 0 然后执行 break 跳出循环，我们使用 compare(e, p) <= 0 然后执行 break 跳出循环。

既然 JDK 的判断方式与我们相反，那么 JDK 是采用 最小堆 来实现优先级队列的。

至于为什么使用最小堆，其实无需纠结，最大堆和最小堆之间本就可以相互转换，因此用谁实现都可以（具体转换可以前往上一篇文章 二叉堆 中查看🏃）。