数据结构（三）-- 优先队列

什么是优先队列？

我们在前几篇文章中学习过了“队列”这种数据结构。那么优先队列和普通队列有什么区别的呢？普通队列的特点是“先进先出”，优先队列则不一样，它的入队顺序没有变化，但是出队的顺序是根据优先级的高低来决定的。优先级高的优先出队。

本文首发于心安-XinAnzzZ 的个人博客，转载请注明出处~

举个生活中的小栗子。病人去医院看病，正常情况下都是需要取号排队，这是普通队列。但是特殊情况下，有一个情况紧急的病人突然来了，这个病人就拥有优先权，他就优先出队，这就是优先队列。

再比如说，玩过LOL的同学都知道，游戏里面防御塔都有一个自动攻击功能，小兵排着队进入防御塔的攻击范围，这时候大炮车的优先级更高（因为系统判定大炮车对于防御塔的威胁更大），所以防御塔会优先攻击大炮车。而当大炮车阵亡，剩下的全部都是普通小兵，这时候离得近的优先级越高，防御塔优先攻击距离更近的小兵。

希望通过这两个小栗子，各位同学能够明白优先队列是怎么一回事，从而更好的理解后面的内容。

• 各种不同的底层数据结构所对应的时间复杂度

	入队	出队（取出最大元素）
普通线性结构	O(1)	O(n)
顺序线性结构	O(n)	O(1)
堆	O(logn)	O(logn)

我们假设有一个优先队列，它的优先级是元素越大优先级越高，也就是每次出队的是队列中值最大的元素。那么如果我们使用普通的线性结构（比如数组和链表）来实现，那么入队的操作，直接插入即可，时间复杂度是O(1)，出队我们需要进行遍历整个队列找到最大元素，然后出队，时间复杂度是O(n)。而如果使用顺序的线性结构（顺序线性结构指的是数据已经有了顺序，比如二分搜索树，中序遍历就是有序的），入队的时候需要进行遍历整个队列来找到合适的位置来插入这个元素，时间复杂度是O(n)，出队的时候由于有序，所以直接取出，时间复杂度是O(1)。我们知道，O(n)的时间复杂度是效率比较低的，所以我们接下来介绍一种入队和出队都是O(logn)时间复杂度的数据结构--堆。

堆

• 完全二叉树

有一定基础的同学对这个概念应该不会陌生，这里还是贴上完全二叉树的百度百科。概念性的东西我不解释太多，大家自己去体会和理解。这里我只说自己的理解，也是我认为最简单的理解。

一棵树，元素从左往右、从上到下依次排列，中间不能有空缺，就是一个完全二叉树。这里要注意区分完全二叉树和满二叉树的区别。如下图：这棵树拥有10个元素，这10个元素从上到下、从左到右依次排列，这就是一个完全二叉树。假如说6、7、8、9这四个位置任意一个位置元素为空，那么就不是完全二叉树。 image

• 二叉堆

二叉堆是特殊的完全二叉树。它满足“堆中任意一个节点的值都不大于其父亲节点的值”这一特征。当然，这个“不大于”是由我们来定义的，我们也可以定义为“不小于”。如果是“不大于”，那么形成的就是“最大堆”，反之就是“最小堆”。下面就是一个最小堆和一个最大堆。注意一个误区，在最大堆当中，堆中任意一个节点的值都不大于父亲节点的值，是否意味着层次越低的节点值越大呢？这是不一定的。

image image

• 二叉堆的数组实现

上面我们说了，二叉堆是一个完全二叉树，就是一个一个元素从左到右、从上到下依次排列出来的，那也就可以使用数组的方式来表示二叉堆。用数组来表示一个二叉堆要解决的问题就是，我们如何找到一个节点的左右孩子。如果我们使用的是树的形式来表示的话，我们是可以通过一个“指针”来表示它的左右孩子，但是数组是没有“指针”的，应该如何实现呢？仔细观察一下下图，我对这个二叉堆从上到下、从左到右进行了编号，编号就代表了元素在数组中的索引，我们可以发现，节点编号满足以下规律：

parent(i) = (i - 1) / 2 left child(i) = 2 * i + 1 right child(i) = (i + 1) * 2

image

1. 下面我们新建一个工程，创建名为MaxHeap（最大堆）的类在里面加入以下代码，这里我们底层依赖ArrayList。

<pre spellcheck="false" class="md-fences md-end-block md-fences-with-lineno ty-contain-cm modeLoaded" lang="java" cid="n49" mdtype="fences" style="box-sizing: border-box; overflow: visible; font-family: Monaco, Consolas, "Andale Mono", "DejaVu Sans Mono", monospace; margin-top: 0px; margin-bottom: 20px; background-image: inherit; background-size: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: inherit; font-size: 0.9rem; display: block; break-inside: avoid; text-align: left; white-space: normal; position: relative !important; padding: 10px 30px 10px 0px; border: 1px solid; width: inherit; background-position: inherit inherit; background-repeat: inherit inherit;"> public class MaxHeap<E extends Comparable<E>> {
​
private ArrayList<E> data;
​
/*** 根据孩子节点索引获取父节点的索引 /
private int getParentIndex(int childIndex) {
if (childIndex == 0) {
throw new IllegalArgumentException("the root node doesn't have parent node !");
}
return (childIndex - 1) / 2;
}
​
/** 根据父节点索引获取左孩子索引 /
private int getLeftChildIndex(int parentIndex) {
if (parentIndex * 2 + 1 > size() - 1) {
throw new IllegalArgumentException("the parent node doesn't have left child node !");
}
return parentIndex * 2 + 1;
}
​
/** 根据父节点索引获取右孩子索引 */
private int getRightChildIndex(int parentIndex) {
if ((parentIndex + 1) * 2 > size() - 1) {
throw new IllegalArgumentException("the parent node doesn't have right child node !");
}
return (parentIndex + 1) * 2;
}
}</pre>

<pre spellcheck="false" class="md-fences md-end-block md-fences-with-lineno ty-contain-cm modeLoaded" lang="java" cid="n59" mdtype="fences" style="box-sizing: border-box; overflow: visible; font-family: Monaco, Consolas, "Andale Mono", "DejaVu Sans Mono", monospace; margin-top: 0px; margin-bottom: 20px; background-image: inherit; background-size: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: inherit; font-size: 0.9rem; display: block; break-inside: avoid; text-align: left; white-space: normal; position: relative !important; padding: 10px 30px 10px 0px; border: 1px solid; width: inherit; background-position: inherit inherit; background-repeat: inherit inherit;"> public void add(E e) {
data.add(e);
int index = data.size() - 1;
// 如果父节点的值小于新节点的值，进行位置互换
while (index > 0 && data.get(getParentIndex(index)).compareTo(e) < 0) {
data.set(index, data.get(getParentIndex(index)));
data.set(getParentIndex(index), e);
index = getParentIndex(index);
}
}</pre>

<pre spellcheck="false" class="md-fences md-end-block md-fences-with-lineno ty-contain-cm modeLoaded" lang="java" cid="n66" mdtype="fences" style="box-sizing: border-box; overflow: visible; font-family: Monaco, Consolas, "Andale Mono", "DejaVu Sans Mono", monospace; margin-top: 0px; margin-bottom: 20px; background-image: inherit; background-size: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: inherit; font-size: 0.9rem; display: block; break-inside: avoid; text-align: left; white-space: normal; position: relative !important; padding: 10px 30px 10px 0px; border: 1px solid; width: inherit; background-position: inherit inherit; background-repeat: inherit inherit;"> /*** 提取最大值 */
public E extractMax() {
if (data.isEmpty()) {
throw new IllegalArgumentException("The heap is empty !");
}
E result = data.get(0);
E remove = data.remove(size() - 1);
​
if (size() == 0) {
return result;
}
data.set(0, remove);
​
int index = 0;
// 如果说左孩子的索引值小于 size 说明左孩子存在，当左孩子不存在的时候 循环终止
while (getLeftChildIndex(index) < size()) {
// 假设左右孩子中左孩子的值较大
int maxIndex = getLeftChildIndex(index);
​
// 如果右孩子存在且有孩子的值大于左孩子，则最大值的索引等于右孩子
if (getRightChildIndex(index) < size()
&& data.get(maxIndex).compareTo(data.get(getRightChildIndex(index))) < 0) {
maxIndex = getRightChildIndex(index);
}
// 如果当前节点值小于左右孩子节点中较大的那个值，则进行位置互换，否则跳出循环
if (data.get(index).compareTo(data.get(maxIndex)) < 0) {
// 互换位置
E e = data.get(index);
data.set(index, data.get(maxIndex));
data.set(maxIndex, e);
​
index = maxIndex;
} else {
break;
}
}
return result;
}</pre>

<pre spellcheck="false" class="md-fences md-end-block md-fences-with-lineno ty-contain-cm modeLoaded" lang="java" cid="n72" mdtype="fences" style="box-sizing: border-box; overflow: visible; font-family: Monaco, Consolas, "Andale Mono", "DejaVu Sans Mono", monospace; margin-top: 0px; margin-bottom: 20px; background-image: inherit; background-size: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: inherit; font-size: 0.9rem; display: block; break-inside: avoid; text-align: left; white-space: normal; position: relative !important; padding: 10px 30px 10px 0px; border: 1px solid; width: inherit; background-position: inherit inherit; background-repeat: inherit inherit;"> public interface Queue<E> {
​
/**

• inserts the element into the queue
• @param e the element to add
  /
  void enqueue(E e);
  ​
  /*
• remove the head of this queue
• @return the has been removed element
  /
  E dequeue();
  ​
  /*
• get the head of this queue
• @return the element at front of the queue
  /
  E getFront();
  ​
  /*
• get the queue's size
• @return the queue's size
  /
  int size();
  ​
  /*
• whether is empty or not
• @return {@code true} if the queue is empty
  */
  boolean isEmpty();
  }</pre>

<pre spellcheck="false" class="md-fences md-end-block md-fences-with-lineno ty-contain-cm modeLoaded" lang="java" cid="n76" mdtype="fences" style="box-sizing: border-box; overflow: visible; font-family: Monaco, Consolas, "Andale Mono", "DejaVu Sans Mono", monospace; margin-top: 0px; margin-bottom: 20px; background-image: inherit; background-size: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: inherit; font-size: 0.9rem; display: block; break-inside: avoid; text-align: left; white-space: normal; position: relative !important; padding: 10px 30px 10px 0px; border: 1px solid; width: inherit; background-position: inherit inherit; background-repeat: inherit inherit;"> public class PriorityQueue<E extends Comparable<E>> implements Queue<E> {
​
private MaxHeap<E> maxHeap;
​
public PriorityQueue() {
this.maxHeap = new MaxHeap<>();
}
​
@Override
public void enqueue(E e) {
maxHeap.add(e);
}
​
@Override
public E dequeue() {
return maxHeap.extractMax();
}
​
@Override
public E getFront() {
return maxHeap.getMax();
}
​
@Override
public int size() {
return maxHeap.size();
}
​
@Override
public boolean isEmpty() {
return maxHeap.isEmpty();
}
}</pre>

示例代码Github

好了，本文就到此为止了。后续的博文会为大家带来LeetCode上面的一道题目，就是使用本文的最大堆来解决的，到时候可以看一下最大堆的实际应用。 谢谢观看~~

2. 具体实现

3. 定义队列接口

以最大堆为底层实现优先队列

以上就是使用数组来实现一个最大堆的核心代码，下面我们以这个最大堆为基础实现一个优先队列。

移除最大元素代码如下：

image

由于堆的特殊性，所以我们取出元素只会取出堆中的最大元素，毕竟人家名字就叫“最大堆”。由于堆的性质，最大元素其实就是根元素，如果移除根元素，那么就不再是一个树了，解决办法是移除根元素之后将堆中最后一个元素放到根元素的位置，但是这样就不再满足堆中元素不大于父节点元素这一性质了。 所以之后一步的操作是用新的根元素和左右孩子中较大的元素进行比较，然后和较大的元素进行互换，直到新的根元素不小于左右孩子为止，这样删除最大节点之后的树就还能满足堆的性质了。这个过程我们称为“Sift down”，即下沉。 下面使用图解和代码来演示如何从取出堆中最大元素。

3. 从堆中移除最大元素

然后我们就可以编写添加元素的代码了：

image

一般来讲，如果新添加的元素大于其父亲节点，那么将这个元素和其父亲节点进行位置互换，如果仍然大于其父亲节点，继续互换，直到不大于父节点为止。 在数据结构中，我们将这个过程称之为“Sift up”，翻译过来就是上浮。下图展示了“上浮”的过程。

通过上面的的概念可以知道，向堆中添加一个元素只需要在最后一个元素后面添加一个元素，这个在数组的操作中是非常简单的。但是如果添加的元素比父亲节点大，那么就不再满足二叉堆的性质，这个问题应该如何解决呢？

2. 向堆中添加一个元素。

首先，我们的类中的元素需要具有可比性，所以我们的元素需要是Comparable接口的子类。成员变量data用来装载堆中的数据，它使用的是ArrayList。然后根据上面我们得到的公式，写出了“根据子节点得到父节点索引”以及“根据父节点得到子节点”的方法，这三个方法在后面的增删等操作中尤为重要。