堆
堆（Heap）是计算机科学中一类特殊的数据结构，通常是一棵完全二叉树（每个结点只有不超过两个子结点，只有最下边一层从右开始不缺少或连续缺少一段结点，其它层都是满的的树形结构）。
堆的性质：
- 某个结点的值总是不大于或不小于其父节点的值
- 通常是个完全二叉树
将根结点最大的堆叫做大根堆，根结点最小的堆叫做小根堆。常见的堆有二叉堆、斐波那契堆等。
左是小根堆，右是大根堆：
堆的定义如下：
\(n\) 个元素的序列 \(\{A_1,A_2,A_i,\cdots,A_n\}\) 当且精当，满足如下条件时，称之为堆：
\[A_i\le A_{2i},A_i\le A_{2i+1} \]或
\[A_i\ge A_{2i}, A_i \ge A_{2i+1}(i=1,2,3,4,5,\cdots,\frac{n}{2}) \]其实这就是把一个结点 \(i\) 的左儿子放在 \(2i\) 的位置，右儿子放在 \(2i+1\) 的位置，然后满足堆的性质。平常储存堆的时候我们也用这种方式储存。
堆的操作
a. 插入：向堆中插入一个新的元素。在数组末尾插入新节点。然后自下而上调整子节点和父节点，如果不满足堆的性质那就调换，使得当前子树满足二叉堆的性质。时间复杂度为 \(\mathcal{O}(\log n)\)。
void push(int a[], int i, int& n) { //i 为插入的值，n 为插入之前堆的大小
n++; //调整大小
a[n] = i;
int p = n;
while (p > 1 && a[p / 2] > a[p]) {
swap(a[p / 2], a[p]);
p /= 2;
}
return;
}
b. 弹出：删除堆顶元素。先把堆存储的最后一个结点放在堆顶处，然后自下而上调整父节点和子结点，时间复杂度为 \(\mathcal{O}(\log n)\)。
int pop(int a[], int& n) {
int res = a[1]; //记录堆顶元素
a[1] = a[n]; //交换堆顶元素和堆尾元素
n--; //调整大小
int p = 1, t;
while (p * 2 <= n) {
if (p * 2 + 1 > n || a[p * 2] <= a[p * 2 + 1]) { //找到左右孩子最小者
t = p * 2;
} else {
t = p * 2 + 1;
}
if (a[p] > a[t]) { //不满足堆的性质
swap(a[p], a[t]);
} else {
break;
}
}
return res;
}
c) 删除：使该元素与堆尾元素交换，调整堆容量，再由原堆尾元素的当前位置自顶向下调整。时间复杂度为 \(\mathcal{O}(\log n)\)。
大根堆
下面序列中符合大根堆的定义的有：
-
7,5,6,2,4,1,5
每个结点都不小于子结点的值
-
7,7,5,7,7,5,5
每个结点都不小于子结点的值
-
7,7,6,8,2,5,3
7和8的关系不符合堆的性质
-
1,2,3,4,5,6,7
小根堆
优先队列
在队列中，元素从队尾进入，队首删除、相比队列，优先队列里的元素增加了优先级的属性，优先级高的元素先被删除。优先队列内部是用堆实现的。
优先队列的使用和队列基本上没有区别。
#include<queue>
#include<iostream>
using namespace std;
int main() {
priority_queue<int> q; //定义一个储存 int 类型的优先队列
q.push(1); //入队
q.push(2);
q.push(3);
while (!q.empty()) {
cout << q.top() << endl;
q.pop();
}
return 0;
}
输出为：
3
2
1
优先队列会默认把较大的数值放在队首，它就是大根堆，想要把较小的值放入前面的话，需要如下的方式定义：
priority_queue<int, vector<int>, greater<int> > pq;
含义是：这个优先队列里装int，这个优先队列内部用vector存储，比较方式是greater，在使用优先队列的时候用greater的方式比较会把较小的元素放在队首
或者，我们也可以使用优先级重载小于号来实现。
struct node {
int dist, loc;
node() { }
bool operator < (const node & a) const {
return dist > a.dist;
}
};
priority_queue <node> Q;
上述代码起到优先级重载的作用，我们仍然可以进行top、pop等便捷的操作。
例题：
输入 \(n\) 个数字，要求从大到小进行排序，必须使用优先队列来实现。
#include<queue>
#include<iostream>
using namespace std;
priority_queue<int> pq;
int main() {
int n;
cin >> n;
for (int i = 1;i <= n;i++) {
int t;
cin >> t;
pq.push(t);
}
while (!pq.empty()) {
cout << pq.top() << endl;
pq.pop();
}
}
合并果子
在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。
每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过 \(n-1\) 次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。
因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为 \(1\) ，并且已知果子的种类 数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。
解析：
每次进行操作的时候，应当选择最少的两堆果子进行合并，直到最后只剩下一堆果子的时候会最优。那就可以使用小根堆进行实现。每次的操作就是量词取出堆顶，然后把他们的和加入答案。最后剩下一堆果子就是答案。
关于其正确性，可以这样来证明。把合并的路径画下来成为一棵树，发现消耗的总体力数就是这一堆的果子数乘上它到根的路径长度。想要这个乘积的和最小，一定是每次合并两堆当前最小的果子。为什么是对的，考虑交换两棵子树，结果要不然跟之前同构，要不然一定是把一权值较大的放到了更深的位置，而权值更小的到了更浅的位置，那答案肯定不会减。按照这样的合并方式画出的树叫做哈夫曼树。
#include <queue>
#include <iostream>
using namespace std;
priority_queue<int, vector<int>, greater<int> > pq;
int main() {
int n;
cin >> n;
for (int i = 0;i < n;i++) {
int t;
cin >> t;
pq.push(t);
}
int ans = 0;
while (pq.size() > 1) {
int n1 = pq.top();
pq.pop();
int n2 = pq.top();
pq.pop();
pq.push(n1 + n2);
ans += n1 + n2;
}
cout << ans << endl;
}
n 个最小和
给出两个长度为 \(n\) 的数组 \(A,B\)。在 \(A,B\) 中任意取出一个数字并将这两个数字相加，可以得到 \(n^2\) 个和，求这些和中最小的 \(n\) 个。
我们可以借助优先队列来解决这题。首先把 \(A,B\) 按照从小到大的顺序排序。观察下面这个表格。
表1：\(A_1+B_1\le A_1+B_2\le A_1 + B_3\le\cdots\le A_1+B_n\)
表2：\(A_2+B_1\le A_2+B_2\le A_2 + B_3\le\cdots\le A_2+B_n\)
表3：\(A_3+B_1\le A_3+B_2\le A_3 + B_3\le\cdots\le A_3+B_n\)
\(\cdots\)
表n：\(A_n+B_1\le A_n+B_2\le A_n + B_3\le\cdots\le A_n+B_n\)
我们使用一个结构 \((sum,a,b)\) 来表示一个和值。
我们建立一个优先队列 \(q\)，队列中 \(sum\) 越小优先级越高。初始的时候将 \((A[i]+B[1],i,1)\) 入队、然后在队列中取出结构 \((sum,a,b)\)，然后把结构 \((A[a],B[b+1],a,b+1)\) 入队。这样重复 \(n\) 次取出的结构就是最小的 \(n\) 个和。任何时候，优先队列最多只会有 \(n\) 个元素，所以时间复杂度为 \(\mathcal{O}(n\log n)\)。
#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
struct node {
int sum, a, b;
node(){}
node(int ssum, int aa, int bb) {
sum = ssum, a = aa, b = bb;
}
bool operator < (const node& rhs) const {
if (sum != rhs.sum) return sum > rhs.sum;
else return a > rhs.a;
}
};
int a[1010], b[1010];
priority_queue<node> pq;
int main() {
int n;
cin >> n;
for (int i = 1;i <= n;i++) cin >> a[i];
for (int i = 1;i <= n;i++) cin >> b[i];
sort(a + 1, a + n + 1);
sort(b + 1, b + n + 1);
for (int i = 1;i <= n;i++) {
pq.push(node(a[i] + b[1], i, 1));
}
for (int i = 1;i <= n;i++) {
node t = pq.top();
pq.pop();
cout << t.sum << ' ';
if (t.b + 1 <= n) {
pq.push(node(t.a) + b[t.b + 1], t.a, t.b + 1);
}
}
return 0;
}
映射二叉堆
具有映射功能的堆称为双向映射堆。堆又名二叉堆，所以也常常称其为映射二叉堆。映射二叉堆相比普通的堆，核心功能是支持元素的快速查找，可以在 \(\mathcal{O}(\log n)\) 的时间复杂度内找到索引为 \(id\) 的元素，并进行后续的修改或者删除等操作。
映射二叉堆与普通堆的不同之处是它不存储数值，而是存储数据对应的索引（数组下标）。当需要比较父子结点的大小时，我们需要对两个索引对应的关键字进行比较；当需要交换父子结点时，我们要交换堆中父子结点的索引。在堆的外部还需要存储一个从索引到堆中元素的反向映射，用来在堆中检索指定索引的元素，进行后续的修改或删除操作。