数据结构：堆
堆
若有树，任取其某一局部，都满足根节点大于等于子节点，则这个树是一个最大堆。同理有最小堆。
如何建堆
建立小根堆的例子：（下面用方括号指出调整的根）
建立堆的过程，颇有分形艺术的感觉。首先我们跳过最末元素 49, 27, 13, 76，因为它们是叶子节点，对于每一个，自身已经是堆——因为没有子节点。因此调整的起点是第 $\lfloor n / 2\rfloor$ 个元素，也即 0 起的 v[n/2 - 1]
1let v = [49, 38, 65, 97, 76, 13, 27, 49]
2/*
3 49
4 / \
5 38 65
6 /\ / \
7 [97] 76 13 27 // 调整的起点是 97
8 /
949
10*/
目标是将 97 的子树（
97
/
49
）变成堆：
1/*
2 49
3 / \
4 38 [65] // 然后我们处理 97 的前一个元素 65
5 /\ / \
6 49 76 13 27
7 /
897
9
10 49
11 / \
12 [38] 13 // 处理再往前一个元素
13 /\ / \
14 49 76 65 27
15 /
1697
17
18 [49] // 处理再往前一个元素
19 / \
20 38 13
21 /\ / \
22 49 76 65 27
23 /
2497
25
26 13
27 / \
28 38 [49] // 如果与子节点发生了交换，那么子节点所在树要重新调整
29 /\ / \
30 49 76 65 27
31 /
3297
33
34
35 13
36 / \
37 38 27
38 /\ / \
39 49 76 65 49
40 /
4197
42
43完成，构成了小根堆，并找出了最小元素 13.
44
45*/
将无序序列顺存，当作完全二叉树。
所有叶子已经是堆（无子节点，相当于子节点是 0），从最后一个非叶子进行调整。
-
如何找到最末非叶子？就是
N/2向下取整。 -
调整哪里？以最末非叶为根的子树调整。
-
如何调整？挑选儿子其中更小的，与自己比较然后交换！（建立小根堆，则交换使得根更小）
- 如果交换了，那么要检查交换后的子节点的树，可能需要重新调整。
-
调整完呢？调整之后的最末非叶子！（
N/2 - 1）
如此处理直到根节点搞定。一轮之后，根将会变成最小元素。
如何调整堆
拿出 H 的根（输出），然后把 last(H) 作为新根。
比较新根的左右孩子，同其中更小的交换。交换之后它的孩子变了，如果还有孩子，就继续执行这一步。
堆排序
如何利用建堆实现堆排序？前面的例子看出，堆排序能够选择出最小的元素。那么对于剩余的元素，再次进行堆排序，可以选择出第二小的元素。
-
初始堆化的时间：$O(n)$
-
一次堆化的时间（插入性能）：$O(\log n)$
-
n-1 次循环时间（排序性能）：$O(n\log n)$
因此时间复杂度为 $O(n) + O(n \log n ) = O(n \log n)$
练习
912. 排序数组 - 力扣（LeetCode） (leetcode-cn.com)
参考实现：
1#include <debug.h>
2
3void adjust(vector<int> &v, int bound, int i) {
4 // 子节点索引
5 int i_left = 2 * i + 1;
6 int i_right = i_left + 1;
7 // 选出比根大的子节点
8 int i_max = i;
9 i_max = i_left < bound && v[i_left] > v[i_max] ? i_left : i_max;
10 i_max = i_right < bound && v[i_right] > v[i_max] ? i_right : i_max;
11 if (i_max != i) {
12 // 让小的靠根
13 swap(v[i_max], v[i]);
14 // 调整变化后的子树
15 adjust(v, bound, i_max);
16 }
17}
18
19void heap_sort(vector<int> &v) {
20 // 构建大根堆
21 int n = v.size();
22 for (int i = n / 2 - 1; i >= 0; i--) {
23 adjust(v, n, i);
24 }
25 // 选择排序
26 for (int i = n - 1; i != 0; i--) {
27 swap(v[0], v[i]);
28 adjust(v, i, 0);
29 }
30}
31
32class Solution {
33public:
34 vector<int> sortArray(vector<int> &nums) {
35 vector<int> ret(nums);
36 heap_sort(ret);
37 return ret;
38 }
39};
40
41int main(int argc, char const *argv[]) {
42 Solution s;
43 vector<int> arr = {8, 1, 14, 3, 21, 5, 7, 10};
44 auto sorted = s.sortArray(arr);
45 print_vec(sorted);
46 return 0;
47}
优先队列
优先队列中的每个元素都有各自的优先级，优先级最高的元素最先得到服务；优先级相同的元素按照其在优先队列中的顺序得到服务。优先队列往往用**堆**来实现。
优先队列至少需要支持下述操作：
插入带优先级的元素（insert_with_priority）
取出具有最高优先级的元素（pull_highest_priority_element）
查看最高优先级的元素（peek）：O(1) 时间复杂度
其它可选的操作：
检查优先级高的一批元素
清空优先队列
批插入一批元素
合并多个优先队列
调整一个元素的优先级
——优先队列
我们先看看 C++ 自带的优先队列怎么用。
C++ 优先队列
头文件：#include<queue>
下面定义一个升序优先队列。队列顶部是最小的。
1priority_queue <int,vector<int>,greater<int> > q_asc;
2// 送入值，送的过程中自动排好序
3q_asc.push(...);
4// 取出队中最小值
5auto min_of_q = q_asc.top();
样例（P215 解）：
1#include <debug.h>
2#include <queue>
3class Solution {
4public:
5 int findKthLargest(vector<int> &nums, int k) {
6 priority_queue<int, vector<int>, greater<int>> q;
7 for (auto num : nums) {
8 // 随便送入 k 个数字到 q
9 if (q.size() != k) {
10 q.push(num);
11 }
12 // 然后把最小的换走，剩下 k 个最大的
13 else {
14 auto min_of_q = q.top();
15 if (num > min_of_q) {
16 // 置换
17 q.pop();
18 q.push(num);
19 }
20 }
21 }
22 return q.top();
23 }
24};
25
26int main(int argc, char const *argv[]) {
27 Solution s;
28 vector<int> v = {3, 2, 3, 1, 2, 4, 5, 5, 6};
29 cout << s.findKthLargest(v, 4) << endl;
30 return 0;
31}