在电影院，相信你也看到有人持有 VIP 卡，可以直接越过队列进场去看电影。对于这种情况，我们的程序也可以用优先级队列（Priority Queue）来模拟这个场景。 通常而言，优先级队列都是基于堆（Heap）这种数据结构来实现的。因此，我们在正式开始学习优先级队列之前，还需要深入浅出地介绍一下堆及其相关的四种操作。
堆
FIFO 队列能够解决广度遍历、分层遍历类似的题目，FIFO 队列在遍历的时候，有一个有趣的特点：每一层结点的先后顺序，遍历时就确定下来了。
如果把这种先后顺序当成优先级，那么这些结点之间的优先级就由遍历时的顺序决定。但是有时候我们遇到的问题，结点之间需要按照大小进行排序之后，再决定优先级。在这种情况下，FIFO 队列不再适用，就需要用一种新的数据结构——优先级队列。
优先级队列底层依赖的数据结构一般是堆，而堆是面试中经常遇到的考点之一。因此，在这里我会先介绍堆的实现与要点，再介绍优先级队列的特点以及具体如何运用。
堆的分类：大堆与小堆
通常堆的结构都是表现为一棵树，如果根比左右子结点都大，那么称为大堆。如下图所示：
如果根比左右子结点都要小，那么称为小堆，如下图所示：
通过堆的定义，可以发现堆的特点：大堆的根是最大值，小堆的根是最小值。
更有趣的是，每次有元素 push 或者 pop 的时候，调整堆的时间复杂度为 O(lgn)，速度也非常快。因此，堆经常被用于优先级队列。接下来，我将以大堆为例，详细介绍堆的表示方式、添加元素、移除元素。
注：后面的堆操作都是基于大堆。
堆的表示
大部分时候都是使用数组表示一个堆，而不是使用二叉树。这是因为: 数组的内存具有连续性，访问速度更快； 堆结构是一棵完全二叉树。 如下图所示，堆的规律有如下几点： 
i 结点的父结点 par = (i-1)/2 i 结点的左子结点 2 * i + 1 i 结点的右子结点 2 * i + 2
堆的操作
堆的操作实际上只有两种：下沉和上浮，如下图所示： 
通过下沉和上浮，又可以分别得到 pop 和 push 操作，接下来我们一起讨论这四种操作的特点。 假设我们已经申请了数组 a[] 和元素 n 表示当前堆中元素的个数，代码如下：
int[] a = new int[100]; // 表示堆的数组空间, 100作示例大小
int n = 0; // 堆中元素个数
注：这个数组的大小仅作为示例讲解，你可以根据实际情况调整，我们的重点是把算法讲清楚。
1. 下沉
引起下沉操作的原因：假设 a[i] 比它的子结点要小，那么除 a[i] 以外，其他子树都满足堆的性质。这个时候，就可以通过下沉操作，帮助 a[i] 找到正确的位置。
注意，上述操作的是大堆。
为了方便你理解，我制作了下沉过程的动图演示，如下图所示： 
Step 1. 结点 3 需要下沉。 Step 2. 将要下沉的值存入变量 t 中，腾出空位。 Step 3. 在子结点 8 和 9 中选中较大的结点 9。 Step 4. 9 比 3 大，9 需要上移，腾出空位。 Step 5. 上移之后，再查看子结点 4 与 7，选中较大结点 7。 Step 6. 由于 7 比 3 大，7 需要上移，腾出空位。 Step 7. 将 3 填入最终空出来的空位中。
首先，写下沉代码时，需要记住一个贪心原则：如果子结点大，那么子结点就要上移。实际上，如果我们将移动路径一维化，那么这段下沉代码就会变成如下图所示的样子： 
Step 1. 最大堆，结点 3 需要下沉。 Step 2. 用临时变量 t 保存值 3。 Step 3.子结点 9 比 t = 3 大，向前移动。 Step 4.接着子结点 7 比 t = 3 大，向前移动。 Step 5.最终给 3 找取最终的位置。 可以发现，下沉与经典的插入排序（递减）非常相似。只有一点略有不同：插入排序是一维的，只与后继的元素进行比较，而下沉是二维的，需要在两个后继元素中找到最大值与插入值进行比较。 根据这个原则，可以写出下沉的代码如下（解析在注释里）：
private void sink(int i) {
int j = 0;
int t = a[i];
// 找到i结点的左子结点
while ((j = (i << 1) + 1) < n) {
// 比插入排序多出来的一步：需要在两个后继中找个最大的出来
// j < n - 1判断是否有右子结点
// 如果有，并且右子结点更大，那么
// j指向右子结点
if (j < n - 1 && a[j] < a[j + 1]) {
j++;
}
// 如果子结点比t大
// 那么t的位置还需要往后排
if (a[j] > t) {
a[i] = a[j];
i = j;
} else {
// 找到了t的位置
// 此时t是大于所有的子结点的
break;
}
}
// 将t放在找到的位置那里
a[i] = t;
}
复杂度分析：由于堆是一个完全二叉树，所以在下沉的时候，下沉路径就是树的高度。如果堆中有 N 个元素的话，所以时间复杂度为 O(lgN)。
2. 上浮
上浮操作的条件：假设 a[i] 比它的父结点要大，并且除 a[i] 以外，其他子树都满足大堆的性质。 注意，上述操作的是大堆。 为了方便你理解，我同样制作了上浮过程的动图演示，如下图所示： 
Step 1.结点 10 太大，需要上浮。 Step 2.将要上浮的 10 放到临时变量 t 中，腾出空位。 Step 3.找到空位的父结点 8。 Step 4.由于 8 比 t = 10 小，所以 8 往下移，腾出空位。 Step 5.选中空位的父结点 9。 Step 6.由于 9 仍然比 10 小，腾出空位。 Step 7.再也不能找到父结点了，将 10 放到空位中。 同样，在上浮的时候，可以发现一个原则：如果父结点比"我"小，那么父结点就需要下移。我们将移动路径一维化，这段插入代码就会变成如下图所示的样子： 
Step 1.最大堆，结点 10 需要上浮。 Step 2.将需要上浮的 10 放到临时变量 t 中，腾出空位。 Step 3.8 比 t 小，移动 8，腾出空位。 Step 4.9 比 t 小，移动 9，腾出空位。 Step 5.不能再移动了，将 t 放到空位中。 可以发现，上浮与经典的插入排序（递减的）非常相似。到这里，结点 a[i] 上浮的代码也比较容易搞定了。
// 上浮
private void swim(int i) {
int t = a[i];
int par = 0;
// 如果还存在父结点
// 由于我们的下标是从0开始
// 0结点没有父结点
while (i > 0) {
par = (i - 1) >> 1;
// 如果父结点比t值小
if (a[par] < t) {
// 那么向下移动父结点的值。
a[i] = a[par];
i = par;
} else {
break;
}
}
a[i] = t;
}
复杂度分析：由于堆是一个完全二叉树，所以在上浮的时候，上浮路径就是树的高度。如果堆中有 N 个元素的话，所以时间复杂度为 O(lgN)。
3. push 操作
需要两步来完成： （1）往堆的尾巴 a[n] 上添加新来的元素 （2）新来元素 a[n] 进行上浮的操作 至此，我们可以写出代码如下（解析在注释里）：
private void push(int v) {
// push是先把元素追加到数组尾巴上，然后再执行上浮操作
a[n++] = v;
swim(n - 1);
}
复杂度分析：主要是上浮操作，所以时间复杂度为 O(lgN)。
4. pop 操作
需要以下 3 步： （1）取出 a[0] 的值作为返回值 （2）然后将 a[n-1] 存放至 a[0] （3）将 a[0] 进行下沉操作 有了 sink() 函数，操作还是比较简单的，我们可以直接写出代码如下：
private int pop() {
int ret = a[0];
a[0] = a[--n];
sink(0);
return ret;
}
复杂度分析：主要是下沉操作，所以时间复杂度为 O(lgN)。 堆的操作都梳理完成之后，这里我们给出完整的代码。虽然是一块比较基础的代码，但是我曾经在商汤的面试中就遇到过这么"裸"的面试题："实现堆的 push 和 pop"。
class Heap {
private int []a = null;
private int n = 0;
// 下沉
public void sink(int i) {
int j = 0;
int t = a[i];
// 找到i结点的左子结点
while ((j = (i << 1) + 1) < n) {
// j < n - 1判断是否有右子结点
// 如果有，并且右子结点更大，那么
// j指向右子结点
if (j < n - 1 && a[j] < a[j + 1]) {
j++;
}
// 如果子结点比t大
// 那么t的位置还需要往后排
if (a[j] > t) {
a[i] = a[j];
i = j;
} else {
// 找到了t的位置
// 此时t是大于所有的子结点的
break;
}
}
// 将t放在找到的位置那里
a[i] = t;
}
// 上浮
public void swim(int i) {
int t = a[i];
int par = 0;
// 如果还存在父结点
while (i > 0 && (par = (i - 1) >> 1) != i) {
// 如果父结点比t值小
if (a[par] < t) {
a[i] = a[par];
i = par;
} else {
break;
}
}
a[i] = t;
}
public void push(int v) {
// push是先把元素追加到数组尾巴上，然后再执行上浮操作
a[n++] = v;
swim(n - 1);
}
public int pop() {
int ret = a[0];
a[0] = a[--n];
sink(0);
return ret;
}
public int size() {
return n;
}
}
题目
面试题 17.14. 最小K个数
讲完了堆的四种操作，我们再来看一下如何把知识运用到题目求解和实际工作中。
class Solution {
private int[] a = null;
private int n = 0;
// 下沉
private void sink(int i) {
int j = 0;
int t = a[i];
// 找到i结点的左子结点
while ((j = (i << 1) + 1) < n) {
// j < n - 1判断是否有右子结点
// 如果有，并且右子结点更大，那么
// j指向右子结点
if (j < n - 1 && a[j] < a[j + 1]) {
j++;
}
// 如果子结点比t大
// 那么t的位置还需要往后排
if (a[j] > t) {
a[i] = a[j];
i = j;
} else {
// 找到了t的位置
// 此时t是大于所有的子结点的
break;
}
}
// 将t放在找到的位置那里
a[i] = t;
}
// 上浮
private void swim(int i) {
int t = a[i];
int par = 0;
// 如果还存在父结点
while (i > 0 && (par = (i - 1) >> 1) != i) {
// 如果父结点比t值小
if (a[par] < t) {
a[i] = a[par];
i = par;
} else {
break;
}
}
a[i] = t;
}
private void push(int v) {
// push是先把元素追加到数组尾巴上，然后再执行上浮操作
a[n++] = v;
swim(n - 1);
}
private int pop() {
int ret = a[0];
a[0] = a[--n];
sink(0);
return ret;
}
private int size() {
return n;
}
public int[] smallestK(int[] arr, int k) {
if (k<0 ||arr.length==0 || arr==null){
return new int[0];
}
a = new int[k+1];
n=0;
for(int num:arr){
push(num);
if(size()>k){
pop();
}
}
int ans[] = new int[k];
int i = 0;
while(size()>0){
ans[i++] = pop();
}
return ans;
}
}
参考链接
- 拉勾教育《数据结构与算法面试宝典》