算法模版：模拟数据结构之堆
定义
堆：是一种满足插入、删除、查询最值的数据结构。
其实是一颗满足堆性质的完全二叉树。
树中的任意一个结点的权值都小于等于父节点，则该二叉树满足"大根堆性质"
大根堆的最大值为根节点的权值。
树中的任意一个结点的权值都大于等于父节点，则该二叉树满足"小根堆性质"
小根堆的最小值为根节点的权值。
存储
层次序列储存方式，即用数组保存二叉堆，
逐层从左到右把树中的节点依次编号，把编号作为节点映射到数组的中下标
从1开始标号
2 * i 为左儿子
2 * i +1 为右儿子
所以父节点编号等于子节点编号除以2
核心操作
down（x）
小根堆（大根堆）
x与左右儿子做比较 ，如果找处最小（大）的儿子与之交换
void down(int u) { int t = u;//t存储三个结点中存在的最小的结点的下标，初始化为当前结点u if (u * 2 <= siz && h[u * 2] < h[t]) t = u * 2; // 左子节点存在并且小于当前结点，更新t的下标 if (u * 2 + 1 <= siz && h[u * 2 + 1] < h[t]) t = u * 2 + 1;//右子节点存在并且小于当前结点，更新t的下标 if (t != u)//如果t==u意味着不用变动，u就是三个结点中拥有最小值的结点下标，否则交换数值 { swap(h[t], h[u]); down(t); //交换数值后，t这个结点存储原本u的值，u存储存储t的值（三个数中的最小值）。u不用调整了，但t情况不明，可能需要调整。直到它比左右子节点都小 } }
up
小根堆（大根堆）
x与父节点做比较 ，如果父节点小（大），x就与父节点交换
void up(int u) { while(u/2&&h[u/2]<h[u])//如果父节点小于 u { heap_swap(u/2,u); u/=2;//变成它的父节点 } }
五种操作（以小根堆为例）
1、插入一个数
heap[ ++ size] = x; up(size);
在作为插入，然后再不断up，直到移到合适位置
2、删除最小值
heap[1] = heap[size]; size – ;down(1);
先用尾部的叶节点 x 覆盖第一个值，即覆盖最小值
然后删除尾部的叶节点 x
最后不断down（1）（因为曾经覆盖最小值的 x 所在的节点编号就是1）
直到down到 x 回到正确位置
3、删除任意一个元素
heap[k] = heap[size]; size – ;up(k); down(k);
先用尾部的叶节点 x 覆盖要删除的元素 k
然后删除尾部的叶节点 x
因为不确定k的位置，所以 up(k); down(k);一起进行总会回到自己的位置
4、修改任意一个元素
heap[k] = x; up(k); down(k);
直接让要修改的元素赋值即可
然后 up(k); down(k);一起进行总会回到自己的位置
5、求最小值
h[1]
根据小根堆性质h[1]即为最小值
STL实现
map + priority_queue（优先队列）
实现可以修改任意位置的堆
在大多数情况下，我们只需要使用STL中的priority_queue即可，万不得已也可以手写左偏树
那么要修改任意位置，我自己瞎搞了一个优先级队列+map的方法，AC了本题，就是不知道有没有问题
//ink代表第k个插入的是谁
//knum代表值为x的数有多少个
1.插入第cnt个数x, 常规操作聪明的你一定能看懂
ink[++cnt] = x;
knum[x] ++;
q.push(x);
2.删除集合中的最小值
问题在于我们集合中的最小值可能是已经被删除了的，那么我们需要找到一个最小值x，其knum[x] > 0，其余小于x的数弹出队列即可，然后找到之后
knum[x] --;
3.修改任意位置
直接把第k的插入的数x的个数减一
然后把k个插入的数改为x
然后把当前插入的数的个数加一
再把这个数插入优先级队列
#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 10; int n, m, cnt; map<int, int> ink; map<int, int> knum; priority_queue<int, vector<int>, greater<int> > q; int main(void) { ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); cin >> n; for (int i = 1; i <= n; i ++ ) { string str; int k, x; cin >> str; if (str == "I") { cin >> x; q.push(x); ink[++cnt] = x; knum[x] ++; } else if (str == "PM") { do { x = q.top(); q.pop(); } while (!knum[x]); q.push(x); cout << x << '\n'; } else if (str == "DM") { do { x = q.top(); q.pop(); } while (!knum[x]); knum[x] --; } else if (str == "D") { cin >> k; x = ink[k]; knum[x] --; } else { cin >> k >> x; knum[ink[k]] --; ink[k] = x; knum[x] ++; q.push(x); } } return 0; }
合并果子
在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。
每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过 n−1n-1n−1 次合并之后， 就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。
因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为 111 ，并且已知果子的种类 数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。
例如有 333 种果子，数目依次为 111 ， 222 ， 999 。可以先将 111 、 222 堆合并，新堆数目为 333 ，耗费体力为 333 。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为 121212 ，耗费体力为 121212 。所以多多总共耗费体力 =3+12=15=3+12=15=3+12=15 。可以证明 151515 为最小的体力耗费值。
输入格式
共两行。
第一行是一个整数 n(1≤n≤10000)n(1\leq n\leq 10000)n(1≤n≤10000) ，表示果子的种类数。
第二行包含 nnn 个整数，用空格分隔，第 iii 个整数 ai(1≤ai≤20000)a_i(1\leq a_i\leq 20000)ai(1≤ai≤20000) 是第 iii 种果子的数目。
输出格式
一个整数，也就是最小的体力耗费值。输入数据保证这个值小于 2312^{31}231 。
输入输出样例
输入 #1
3 1 2 9
输出 #1
#include<bits/stdc++.h> using namespace std; int ans,x; priority_queue<int,vector<int>,greater<int>> heap; int main(){ int n; cin>>n; for(int i = 1 ; i <= n ; i++) cin>>x,heap.push({x}); for(int i = 1 ; i <= n - 1; i ++) { int a = heap.top();heap.pop(); int b = heap.top();heap.pop(); ans+=a+b; heap.push({a+b}); } cout<<ans; return 0; }
完结散花
ok以上就是对 模拟数据结构之堆 的全部讲解啦，很感谢你能看到这儿。如果有遗漏、错误或者有更加通俗易懂的讲解,欢迎小伙伴私信我，我后期再补充完善。
