喜欢该类型文章可以给博主点个关注，博主会持续输出此类型的文章，知识点很全面，再加上LeetCode的真题练习，每一个LeetCode题解我都写了详细注释，比较适合新手入门数据结构与算法，后续也会更新进阶的文章。
课件参考—开课吧《门徒计划》

2-2 堆（Heap）与优先队列

堆是我们学完二叉树之后，涉及到的第一个基于二叉树基础之上的数据结构。

如果没有学过二叉树建议先去看这篇文章：数据结构学习笔记 2-1 二叉树（Binary Tree）与 LeetCode真题（Java）

堆的基础知识

完全二叉树是唯一可以用数组表示的树，因为它是连续的。

完全二叉树还有一个性质：假设共有 $n$ 个节点，那么前 [ 1 , n 2 ] [1, \frac{n}{2}] [1,2n​] 一定不是叶子节点， ( n 2 , n ] (\frac{n}{2},n] (2n​,n] 一定是叶子节点，在后面的堆会用到这样的性质。

堆的结构定义：

1. 基于完全二叉树的数据结构
2. 每一个节点的值都大于或者小于子节点的值（大根堆/小根堆）

堆的插入

上浮调整

时间复杂度 $O(logN)$

由于我们不能破坏完全二叉树，我们插入时只能插入在数组的末尾，但还未满足我们的第二条性质，所以我们要依次跟父节点比较大小：

我们依次跟父节点进行了三次比较，使得加入的节点位于他应该在的位置。

堆的弹出

下沉调整

时间复杂度 $O(logN)$

我们把堆顶元素弹出之后，剩下的值应该怎么操作呢？我们要保证完全二叉树的性质，把空节点给补上，所以可以直接将末尾数据挪到第一位上：

之后再保证第二个性质，逐步往下调整：

我们不能跟空节点进行调整，如果调整就会破坏完全二叉树的性质，所以我们先拿最后一个元素补上，再一点一点逐层调整位置。

堆排序

时间复杂度 $O(NlogN)$

堆排序的时间复杂度是最稳定的，永远都是$O(NlogN)$。

堆的建立

1. Push建堆

   时间复杂度 $O(NlogN)$

   我们可以用两个数组建立，一个arr[]数组存放初始值，一个heap[]数组负责存放堆的值，每一次从arr[]数组拿到数据放到heap[]后，进行一次调整，其实就是进行上面的插入操作。

2. 原地建堆

   时间复杂度 $O(N)$

   上面我们提到过完全二叉树的性质，此时我们就可以利用这个性质来原地建立堆：假设共有 $n$ 个节点，那么前 [1, n 2 ] [1, \frac{n}{2}][1,2n​] 一定不是叶子节点， ( n 2 ,n] (\frac{n}{2},n](2n​,n] 一定是叶子节点；我们可以这么想象：不管是从上往下调整还是从下往上调整，他们最终的归宿都是第一层或者最后一层，怎么让我们的操作数尽可能的少呢？我们只对非叶子节点进行下沉操作（因为叶子节点沉无可沉）, 根据 n 2 \frac{n}{2}2n​ 的下标来确定最后一个非叶子节点的下标，判断数组中这个坐标以及这个坐标之前的值是否能继续下沉。

时间复杂度分析

原地建堆

s1 =20 × h +21 × ( h − 1 ) +22 × ( h − 2 ) + . . . +2k × ( h − k ) + . . . +2 h − 1 × 1 s_1 = 2^0×h+2^1×(h-1)+2^2×(h-2)+...+2^k×(h-k)+...+2^{h-1}×1 s1​=20×h+21×(h−1)+22×(h−2)+...+2k×(h−k)+...+2h−1×1

经过数学公式化简：

堆的代码实现

import java.util.Scanner;public class Heap {    static final int N = 110;    static int[] data = new int[N];    static int cnt;    public static void main(String[] args) { Scanner sc = new Scanner(System.in); int op = 0, val = 0, num = 0; while (sc.hasNext()) {     op = sc.nextInt();     switch (op) {  case 0: { // 执行插入      num++;      val = sc.nextInt();      System.out.println("push " + val + " to heap");      push(val);  } break;  case 1: { // 执行弹出      System.out.println("pop " + val + " to heap");      pop();  } break;  case 2 : { // 堆排序      for (int i = 0; i < num; i++) {   System.out.print(data[i]);      }      System.out.println();  }     }     output(); }    }// 返回堆顶元素    private static int top() { return data[0];    }// 返回堆的大小    private static int size() { return cnt;    }// 插入    private static void push(int x) { data[cnt++] = x; int ind = cnt - 1; // 存储当前节点下标 while (ind != 0 && data[ind] > data[(ind - 1) / 2]) { // 判断是否大于父节点 并且未到堆顶 上浮     swap(data, ind, (ind - 1) / 2); // 如果大于则交换     ind = (ind - 1) / 2; }    }// 弹出    private static void pop() { if (size() == 0) return; swap(data, 0, cnt - 1); // 头部弹出 末尾值挪到第一位 cnt--; // 删掉最后一位 int ind = 0, n = cnt - 1; while (ind * 2 + 1 <= n) { // 判断ind的左子树有没有值 逐步下沉     int temp = ind; // 暂存ind     if (data[temp] < data[ind * 2 + 1]) temp = ind * 2 + 1; // 如果ind小于左子树 则与左子树交换     if (ind * 2 + 2 <= n && data[temp] < data[ind * 2 + 2]) temp = ind * 2 + 2; // 同理 与右子树交换     if (temp == ind) break; // 如果相等则不需要操作     swap(data, temp, ind); // 此时temp就是根节点以及左右节点中最大的节点 与ind进行交换     ind = temp; // 更新节点 }    }// 输出堆    private static void output() { System.out.print("heap: "); for (int i = 0 ; i < cnt; i++) {     System.out.print(data[i] + " "); } System.out.println();    }// 交换    private static void swap(int[] data, int a, int b) { int t = data[a]; data[a] = data[b]; data[b] = t;    }}

输入输出

堆—优先队列

我们在说堆的时候，一般都会说到优先队列，堆是我们实现优先队列非常常见的方式。

堆只是实现优先队列的一个方法，并不是优先队列只能用堆来实现。

LeetCode真题

经典面试题—堆的基础应用

LeetCode剑指 Offer 40. 最小的k个数

难度：easy

这道题我们利用大根堆来做，我们需要得到前 $k$ 个最小的数，那么我们可以维护一个只有 $k$ 个大小的大根堆，当插入的值的数量为 $k+1$ 时，我们就把堆顶元素弹出，此时弹出的数一定是这 $k+1$ 中最大的一个数，这样遍历完所有的数，最后在堆中的 $k$ 个数一定是最小的数。

用优先队列PriorityQueue实现堆，Java中PriorityQueue默认是小根堆。

LeetCode题解：代码实现

LeetCode1046. 最后一块石头的重量

难度：easy

根据题意用堆来模拟，创建一个大根堆，先取出堆顶元素 $y$，然后再取出一次堆顶元素 $x$，进行比较，如果相等则不进行操作，如果不等则 $y-x$，把这个值再存入堆中。

LeetCode题解：代码实现

LeetCode703. 数据流中的第 K 大元素

难度：easy

这道题跟第一题很像，第一题是输出 $k$ 个数，这题是输出第 $k$ 大个元素类。

但是这道题我们需要用小顶堆来做，同样维护一个 $k$ 大小的小根堆，堆顶存放的是堆中最小的元素，如果此时 $heap.size()>k$，那么我们就将堆顶元素弹出，这样遍历完所有数之后，堆顶元素自然而然的就是第 $k$ 大元素。

LeetCode题解：代码实现

LeetCode373. 查找和最小的 K 对数字

难度：mid

第一题的变形题，查找一对数字(u, v)，u是nums1[]数组中的值，v是nums2[]数组中的值，我们构建堆的时候可以存入一个数组int[]，int[0]是nums1[]数组中的值，int[1]是nums2[]数组中的值，int[2]是两个数的和。

同样基于大根堆，往堆里存值，只要 $heap.size()>k$，就执行 $poll()$ 操作，维护原理与第一题一样，具体参考代及码注释。

LeetCode题解：代码实现

LeetCode215. 数组中的第K个最大元素

难度：mid

其实我们发现，如果求最小值，我们就用大根堆，如果求最大值，我们就用小根堆。

跟前面的题 第 K 大元素 异曲同工，维护 $k$ 个大小的大根堆，直接上代码吧。

LeetCode题解：代码实现

经典面试题—堆的进阶应用

LeetCode692. 前K个高频单词

难度：mid

别看这个题跟上面的题不一样，他其实就是筛出前 $k$ 大个元素，我们维护一个容量为 $k$ 的小顶堆。

如果出现次数相同，则按照字母顺序排序，所以我们在写排序的时候要考虑到字母的排序。

用Map存储字符串以及出现的次数，代码实现较为复杂。

LeetCode题解：代码实现

LeetCode295. 数据流的中位数

难度：hard

这个题是让我们维护一个数据结构，可以很快的返回数据流中的中位数；

如果我们用一个数组的下标来取中位数的话，因为题中是有序数组中的中位数，我们每次要进行一次sort才可以根据下标来取，这样的时间复杂度明显很高。

我们试着用堆来维护中间值。

列表长度是奇数，那中位数就是中间的数，如果列表长度是偶数，那么中位数是中间两个数的平均值，故我们可以维护两个堆：

在插入的时候判断大根堆和小根堆的 $size()$ 差值有没有超过 $1$，先将 $1$ 存入大根堆中，随后要将 $2$ 存入小根堆中，但是到 $3$ 时，我们不能把它直接存入到大根堆中，应该先让小根堆进行 $poll()$ ，然后再 $push()$ 到大根堆中，也就是将 $2$ 存入大根堆中，然后再将 $3$ 存入到小根堆中，这样我们就可以一直保证大根堆中一定是前半部分元素，小根堆中一定是后半部分元素。

这样两个堆的实现方式我们也叫做对顶堆。

LeetCode题解：代码实现

LeetCode264. 丑数 II

丑数 就是只包含质因数 2、3 和/或 5 的正整数。如下图：

我们发现圈红的数在之前都已经出现过了，此时我们发现了一个规律：每一个数在枚举的时候，不需要乘比自己最大质因子还小的质因子了，$3$ 的最大质因子是 $3$，也就是 $3$ 不需要再乘 $2$，$5$ 的最大质因子是 $5$，也就是 $5$ 不需要再乘 $2、3$，对于 $6$， $6$ 的最大质因子是 $3$，那么 $6$ 就不需要再乘 $2$ 了，这样就不会发生重复了。

所以我们可以维护一个小根堆，当 $poll()$ 到第 $n$ 次时就是我们的答案。

LeetCode题解：代码实现

LeetCode313. 超级丑数

上一题的丑数是乘 $235$，而这一题是乘我们的质数数组primes[]中的值。

LeetCode题解：代码实现

LeetCode1753. 移除石子的最大得分

从三堆石子中 每次只能同时取出两堆石子中的一个石子，加 $1$ 分，当有两个或三个石子堆为空，游戏结束，求最大得分。

我们要尽可能的使三堆石子都为空。

当然，我们没有必要按规矩每次拿 $1$ 个，我们可以一次性拿 $n$ 个，使得第二多的堆跟最少的堆石子数量一样；这里用到了贪心思想。

我们可以用堆来实现，每次都在最多的两个堆里拿；但这题堆的数量太小了，堆其实有点大材小用了。

这道题的最优解法其实是数学找规律，因为本章我们主要是堆的操作，所以用堆来做这个题，题解里也写了最优解法。

LeetCode题解：两种方法代码实现

总结

堆的题相对还是比较简单的，比较有意义的题是LeetCode703. 数据流中的第 K 大元素以及LeetCode295. 数据流的中位数，因为这两个题可以进行一些引申：

比如数据流中求第 K 大个元素，它通常会在计算机里问，比如一些文件很大，内存放不下，这时我们应该怎样做一些拆分，此时就可以利用我们的堆来做，我们没有必要记录所有的值，只维护它第 K 大的文件。

比如求中位数那道题，我们可以求 13 \frac{1}{3} 31​ 位数、 14 \frac{1}{4} 41​ 位数等等……

以上两题是比较经典的堆思想实际的应用，但堆中最重要的地方是堆的结构定义和结构操作，以及堆的建立、排序的时间复杂度分析，需要重点关注。