数据结构之优先队列和堆
什么是优先队列
我们都知道队列是一种先进先出、后进后出的数据结构，就如同日常生活中的排队一样，先到先得。而优先队列则是一种特殊的队列，优先队列与普通队列最大的不同点就在于出队顺序不一样。
因为优先队列的出队顺序与入队顺序无关，和优先级有关。也就是按元素的优先级决定其出队顺序，优先级高的先出队，优先级低的后出队，这也是为什么这种数据结构叫优先队列的原因。
这就好比现实生活中在银行排队办理业务，持有金卡的客户可以优先于普通卡的客户被接待，而钻石卡的客户又优先于金卡的客户，以此类推。这就是一种优先队列。
应用场景：
- 优先队列的应用场景非常多，比如，任务调度器、赫夫曼编码、图的最短路径、最小生成树算法等等。不仅如此，很多语言中，都提供了优先级队列的实现，比如，Java 的
PriorityQueue，C++ 的priority_queue等。
堆的基础表示
堆（Heap）简单来说是一种特殊的树，那么什么样的树才是堆呢？我罗列了两点要求，只要满足这两点，它就是一个堆：
- 堆是一个完全二叉树。完全二叉树：把元素顺序排列成树的形状
- 堆中每一个节点的值都必须大于等于（或小于等于）其子树中每个节点的值
第一点，堆必须是一个完全二叉树。还记得我们之前讲的完全二叉树的定义吗？完全二叉树要求，除了最后一层，其他层的节点个数都是满的，最后一层的节点都靠左排列。
第二点，堆中的每个节点的值必须大于等于（或者小于等于）其子树中每个节点的值。实际上，我们还可以换一种说法，堆中每个节点的值都大于等于（或者小于等于）其左右子节点的值。这两种表述是等价的。
对于每个节点的值都大于等于子树中每个节点值的堆，我们叫做“大顶堆”。对于每个节点的值都小于等于子树中每个节点值的堆，我们叫做“小顶堆”。
清楚了定义之后，我们来直观的看一下什么是堆：
在上图中，第 1 个和第 2 个是大顶堆，第 3 个是小顶堆，第 4 个不是堆。除此之外，从图中还可以看出来，对于同一组数据，我们可以构建多种不同形态的堆。
如何实现一个堆？
堆的实现并不局限于某一种特定的方式，可以使用链式树形结构（节点有左右指针）实现，也可以使用数组实现，因为完全二叉树的特性是一层一层按顺序排列的，完全可以紧凑地放在数组中。而且基于数组实现堆是一种比较巧妙且高效的方式，也是最常用的方式。
用数组来存储完全二叉树是非常节省存储空间的。因为我们不需要存储左右子节点的指针，单纯地通过数组的下标，就可以找到一个节点的左右子节点和父节点。如下图所示：
从图中我们可以看到节点的存放规律就是：数组中下标为 i 的节点的左子节点，就是下标为 2∗i 的节点，右子节点则是下标为 2∗i+1 的节点。所以反过来，其父节点也就是下标为 \frac{i}{2} 的节点。
parent(i) = i / 2
left child(i) = 2 * i
right child(i) = 2 * i + 1通过这种方式，我们只要知道根节点存储的位置，这样就可以通过下标计算，把整棵树都串起来。一般情况下，为了方便计算子节点，根节点会存储在下标为 1 的位置。
如果从 0 开始存储，实际上处理思路是没有任何变化的，唯一变化的就是计算子节点和父节点的下标的公式改变了：如果节点的下标是 i，那左子节点的下标就是 2∗i+1，右子节点的下标就是 2∗i+2，父节点的下标就是 \frac{i-1}{2}。如下图所示：
有了以上的认知后，接下来，我们就可以先编写一个堆的基础框架代码了：
package heap;
import java.util.ArrayList;
import java.util.Collections;
/**
* 基于数组实现的最大堆
* 堆中的元素需要具有可比较性，所以需要实现Comparable
* 在此实现中是从数组的下标0开始存储元素，因为使用ArrayList作为数组的角色
*
* @author 01
* @date 2021-01-19
**/
public class MaxHeap<E extends Comparable<E>> {
/**
* 使用ArrayList的目的是无需关注动态扩缩容逻辑
*/
private final ArrayList<E> data;
public MaxHeap(int capacity) {
this.data = new ArrayList<>(capacity);
}
public MaxHeap() {
this.data = new ArrayList<>();
}
/**
* 返回对中的元素个数
*/
public int size() {
return data.size();
}
/**
* 判断堆是否为空
*/
public boolean isEmpty() {
return data.isEmpty();
}
/**
* 根据传入的index，计算其父节点所在的下标
*/
private int parent(int index) {
if (index == 0) {
throw new IllegalArgumentException("index-1 doesn't have parent.");
}
return (index - 1) / 2;
}
/**
* 根据传入的index，计算其左子节点所在的下标
*/
private int leftChild(int index) {
return index * 2 + 1;
}
/**
* 根据传入的index，计算其右子节点所在的下标
*/
private int rightChild(int index) {
return index * 2 + 2;
}
}向堆中添加元素和Sift Up
往堆中添加一个元素后，我们需要继续满足堆的两个特性。如果我们把新添加的元素放到数组的最后，如下图，是不是就不符合堆的特性了？
于是，我们就需要进行调整，让其重新满足堆的特性，这个过程就叫做堆化（heapify）。堆化实际上有两种，从下往上（Sift Up）和从上往下（Sift Down）。这里我先讲从下往上的堆化方法。堆化非常简单，就是顺着节点所在的路径，向上或者向下，对比，然后交换。
看下面这张使用Sift Up方式的堆化过程分解图。我们可以让新插入的节点与父节点对比大小。如果不满足子节点小于等于父节点的大小关系，我们就互换两个节点。一直重复这个过程，直到父子节点之间满足刚说的那种大小关系：
将这个流程翻译成具体的实现代码如下：
/**
* 向堆中添加元素 e
*/
public void add(E e) {
data.add(e);
siftUp(data.size() - 1);
}
/**
* 从下往上调整元素的位置，直到元素到达根节点或小于父节点
*/
private void siftUp(int k) {
while (k > 1 && isParentLessThan(k)) {
// 交换 k 与其父节点的位置
Collections.swap(data, k, parent(k));
k = parent(k);
}
}
/**
* 判断 k 的父节点是否小于 k
*/
private boolean isParentLessThan(int k) {
return data.get(parent(k)).compareTo(data.get(k)) < 0;
}从堆中取出元素和Sift Down
从堆的定义的第二条中，任何节点的值都大于等于（或小于等于）子树节点的值，我们可以发现，堆顶元素存储的就是堆中数据的最大值或者最小值。
而从堆中取出元素其实就是取出堆中最大或最小的元素，并且取出后会删除，所以也可以理解为删除堆顶元素。堆顶也就是堆的根节点，或者说是数组下标为0或1的元素。
假设我们构造的是大顶堆，堆顶元素就是最大的元素。当我们删除堆顶元素之后，就需要把最后一个节点放到堆顶，然后利用同样的父子节点对比方法。对于不满足父子节点大小关系的，互换两个节点，并且重复进行这个过程，直到父子节点之间满足大小关系为止。这就是从上往下（Sift Down）的堆化方法。如下图：
因为我们移除的是数组中的最后一个元素，而在堆化的过程中，都是交换操作，不会出现数组中的“空洞”，所以这种方法堆化之后的结果，肯定满足完全二叉树的特性。
具体的实现代码如下：
/**
* 获取堆顶元素
*/
public E findMax() {
if (isEmpty()) {
throw new IllegalArgumentException("Can't find max when heap is empty.");
}
return data.get(0);
}
/**
* 从堆中取出元素，也就是取出堆顶元素
*/
public E extractMax() {
E ret = findMax();
// 交换根节点与最后一个节点的位置
Collections.swap(data, 0, data.size() - 1);
// 删除最后一个节点
data.remove(data.size() - 1);
siftDown(0);
return ret;
}
/**
* 从上往下调整元素的位置，直到元素到达叶子节点或大于左右子节点
*/
private void siftDown(int k) {
// 左子节点大于size时就证明到底了
while (leftChild(k) < data.size()) {
int leftChildIndex = leftChild(k);
int rightChildIndex = leftChildIndex + 1;
int maxChildIndex = leftChildIndex;
// 左右子节点中最大的节点下标
if (rightChildIndex < data.size() &&
isGreaterThan(rightChildIndex, leftChildIndex)) {
maxChildIndex = rightChildIndex;
}
// 大于最大的子节点证明 k 已经大于左右子节点，无需再继续下沉了
if (data.get(k).compareTo(data.get(maxChildIndex)) >= 0) {
break;
}
// 否则，交换 k 与其最大子节点的位置，继续下沉
Collections.swap(data, k, maxChildIndex);
k = maxChildIndex;
}
}
/**
* 判断右子节点是否大于左子节点
*/
private boolean isGreaterThan(int rightChildIndex, int leftChildIndex) {
return data.get(rightChildIndex).compareTo(data.get(leftChildIndex)) > 0;
}到此为止，我们就已经实现了堆的核心操作。接下来我们使用一个简单的测试用例，测试下这个堆的行为是否符合预期。测试代码如下：
/**
* 测试堆的行为是否符合预期
*/
private static void testAddAndExtractMax() {
int n = 1000000;
// 随机往堆里添加n个元素
MaxHeap<Integer> maxHeap = new MaxHeap<>();
Random random = new Random();
for (int i = 0; i < n; i++) {
maxHeap.add(random.nextInt(Integer.MAX_VALUE));
}
// 取出堆中的所有元素，放到arr中
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = maxHeap.extractMax();
}
// 由于堆的特性，此时arr中的元素理应是有序的
// 所以这里校验一下arr是否是有序的，如果无序则代表堆的实现有问题
for (int i = 1; i < n; i++) {
if (arr[i - 1] < arr[i]) {
throw new IllegalArgumentException("Error");
}
}
System.out.println("Test MaxHeap completed.");
}
public static void main(String[] args) {
testAddAndExtractMax();
}Heapify 和 Replace
堆的 Heapify 和 Replace 也是比较常见的操作，虽然使用之前所编写的代码也能实现，但并不是那么好使，例如实现 Replace 需要两次O(logn)的操作。所以在本小节就为这两个操作，单独编写相应的代码。
Replace
- Replace：取出最大元素后，放入一个新元素
- 使用已有代码的实现：可以先extractMax，再add，两次O(logn)的操作
- 新的实现：可以直接将堆顶元素替换以后进行Sift Down，只需要一次O(logn)的操作
有了之前的代码基础，实现 Replace 就非常简单了，只需要几行代码。如下：
/**
* 取出堆中的最大元素，并且替换成元素e
*/
public E replace(E e) {
E ret = findMax();
// 替换堆顶元素
data.set(0, e);
siftDown(0);
return ret;
}Heapify
- Heapify：将任意数组整理成堆的形状，也就是对一个数组进行堆化，或者说是建堆
- 使用已有代码的实现：遍历数组，调用add将每个元素添加到堆里。时间复杂度是O(nlogn)
- 新的实现：从后往前处理数组，并且每个数据都是从上往下堆化。因为叶子节点往下堆化只能自己跟自己比较，所以我们直接从最后一个非叶子节点开始，依次堆化就行了。这样相当于只需要对数组中一半的元素进行Sift Down操作。时间复杂度是O(n)
建堆分解步骤图如下：
同样，基于之前已有的代码，Heapify 实现起来也非常的简单，我们可以选择在构造器中提供这个功能。具体的实现代码如下：
public MaxHeap(E[] arr) {
this.data = asArrayList(arr);
// 最后一个非叶子节点的下标
int lastNode = parent(data.size() - 1);
for (int i = lastNode; i >= 0; i--) {
// 从后往前依次堆化
siftDown(i);
}
}
/**
* 将数组转换为ArrayList
*/
private ArrayList<E> asArrayList(E[] arr) {
ArrayList<E> ret = new ArrayList<>();
Collections.addAll(ret, arr);
return ret;
}基于堆的优先队列
现在我们已经了解了优先队列和堆，并且自己动手实现了一个堆，因此，不难看得出来，堆和优先队列非常相似。一个堆其实就可以看作是一个优先队列。Java中的优先队列也是基于堆实现的，是一个小顶堆。
很多时候，它们只是概念上的区分而已。往优先队列中插入一个元素，就相当于往堆中插入一个元素；从优先队列中取出优先级最高的元素，就相当于取出堆顶元素。所以，堆和优先队列在基本行为上是等价的。
我们之前也提到了优先队列可以使用不同的方式进行实现，但使用堆这种数据结构来实现优先队列是最高效也最符合直觉的，因为堆本身就是一个优先队列。
从下图中可以看到使用不同数据结构实现优先队列的时间复杂度：
接下来，我们就实现一个基于堆的优先队列。首先，定义一个队列接口：
package queue;
/**
* 队列数据结构接口
*
* @author 01
**/
public interface Queue<E> {
/**
* 新元素入队
*
* @param e 新元素
*/
void enqueue(E e);
/**
* 元素出队
*
* @return 元素
*/
E dequeue();
/**
* 获取位于队首的元素
*
* @return 队首的元素
*/
E getFront();
/**
* 获取队列中的元素个数
*
* @return 元素个数
*/
int getSize();
/**
* 队列是否为空
*
* @return 为空返回true，否则返回false
*/
boolean isEmpty();
}然后实现接口中的方法，由于我们之前已经实现了一个堆，所以这个优先队列实现起来就非常简单了：
package queue;
import heap.MaxHeap;
/**
* 基于堆实现的优先队列
*
* @author 01
* @date 2021-01-19
*/
public class PriorityQueue<E extends Comparable<E>> implements Queue<E> {
private final MaxHeap<E> maxHeap;
public PriorityQueue() {
maxHeap = new MaxHeap<>();
}
@Override
public int getSize() {
return maxHeap.size();
}
@Override
public boolean isEmpty() {
return maxHeap.isEmpty();
}
@Override
public E getFront() {
return maxHeap.findMax();
}
@Override
public void enqueue(E e) {
maxHeap.add(e);
}
@Override
public E dequeue() {
return maxHeap.extractMax();
}
}