堆
1、概念：
A.堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序， 它的最坏、最好、平均时间复杂度均为 O(nlogn)， 它也是不稳定排序。
B.堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值， 这种情况称为大顶堆，注意:没有要求结点的左孩子的值和右孩子的值的大小关系。
C.每个结点的值都小于或等于其左右孩子结点的值， 这种情况称为小顶堆。
D.大顶堆举例说明
E.小顶堆举例说明
一般升序采用大顶堆， 降序采用小顶堆。
2.基本思路：
3.算法模板：
// h[N]存储堆中的值, h[1]是堆顶，x的左儿子是2x, 右儿子是2x + 1 // ph[k]存储第k个插入的点在堆中的位置 // hp[k]存储堆中下标是k的点是第几个插入的 int h[N], ph[N], hp[N], size; // 交换两个点，及其映射关系 void heap_swap(int a, int b) { swap(ph[hp[a]],ph[hp[b]]); swap(hp[a], hp[b]); swap(h[a], h[b]); } void down(int u) { int t = u; if (u * 2 <= size && h[u * 2] < h[t]) t = u * 2; if (u * 2 + 1 <= size && h[u * 2 + 1] < h[t]) t = u * 2 + 1; if (u != t) { heap_swap(u, t); down(t); } } void up(int u) { while (u / 2 && h[u] < h[u / 2]) { heap_swap(u, u / 2); u >>= 1; } } // O(n)建堆 for (int i = n / 2; i; i -- ) down(i);
4.例题：
（1）.堆排序
输入一个长度为 n的整数数列，从小到大输出前 m小的数。
输入格式
第一行包含整数 n和 m。
第二行包含 n 个整数，表示整数数列。
输出格式
共一行，包含 m 个整数，表示整数数列中前 m小的数。
数据范围
1≤m≤n≤10^5，
1≤数列中元素≤10^9
输入样例：
5 3 4 5 1 3 2
输出样例：
1 2 3
#include<iostream> using namespace std; const int N=100010; int h[N]; int n,m; int r; void down(int u) { //t记录最小点的编号 int t=u; //有左儿子，并且左儿子比t节点的值小，更新t if(2*u<=r && h[2*u]<h[t])t=2*u; //有右儿子，并且右儿子比t节点的值小，更新t if(2*u+1<=r && h[2*u+1]<h[t])t=2*u+1; //如果待调整点不是最小的 if(u!=t) { //和最小的交换 swap(h[u], h[t]); //递归处理 down(t); } } int main() { cin>>n>>m; for(int i=1;i<=n;i++)cin>>h[i]; r=n;//开始时，右边界是数组边界 for(int i=n/2;i;i--)down(i); while(m--) { //堆顶保存的最小值，输出堆顶 cout<<h[1]<<" "; //将堆顶和右边界交换 swap(h[1],h[r]); //右边界左移 r--; //从新处理堆顶 down(1); } return 0; }
（2）.模拟堆
维护一个集合，初始时集合为空，支持如下几种操作：
- I x，插入一个数 x；
- PM，输出当前集合中的最小值；
- DM，删除当前集合中的最小值（数据保证此时的最小值唯一）；
- D k，删除第 k个插入的数；
- C k x，修改第 k 个插入的数，将其变为 x；
现在要进行 N 次操作，对于所有第 2 个操作，输出当前集合的最小值。
输入格式
第一行包含整数 N。
接下来 N 行，每行包含一个操作指令，操作指令为 I x，PM，DM，D k 或 C k x 中的一种。
输出格式
对于每个输出指令 PM，输出一个结果，表示当前集合中的最小值。
每个结果占一行。
数据范围
1≤N≤10^5
−109≤x≤10^9
数据保证合法。
输入样例：
8 I -10 PM I -10 D 1 C 2 8 I 6 PM DM
输出样例：
-10 6
#include<iostream> #include<algorithm> using namespace std; const int N=1e5+10; int h[N]; //堆 int ph[N]; //存放第k个插入点的下标 int hp[N]; //存放堆中点的插入次序 int cur_size; //size 记录的是堆当前的数据多少 //这个交换过程其实有那么些绕 但关键是理解 如果hp[u]=k 则ph[k]=u 的映射关系 //之所以要进行这样的操作是因为 经过一系列操作 堆中的元素并不会保持原有的插入顺序 //从而我们需要对应到原先第K个堆中元素 //如果理解这个原理 那么就能明白其实三步交换的顺序是可以互换 //h,hp,ph之间两两存在映射关系 所以交换顺序的不同对结果并不会产生影响 void heap_swap(int u,int v) { swap(h[u],h[v]); swap(hp[u],hp[v]); swap(ph[hp[u]],ph[hp[v]]); } void down(int u) { int t=u; if(u*2<=cur_size&&h[t]>h[u*2]) t=u*2; if(u*2+1<=cur_size&&h[t]>h[u*2+1]) t=u*2+1; if(u!=t) { heap_swap(u,t); down(t); } } void up(int u) { if(u/2>0&&h[u]<h[u/2]) { heap_swap(u,u/2); up(u>>1); } } int main() { int n; cin>>n; int m=0; //m用来记录插入的数的个数 //注意m的意义与cur_size是不同的 cur_size是记录堆中当前数据的多少 //对应上文 m即是hp中应该存的值 while(n--) { string op; int k,x; cin>>op; if(op=="I") { cin>>x; m++; h[++cur_size]=x; ph[m]=cur_size; hp[cur_size]=m; //down(size); up(cur_size); } else if(op=="PM") cout<<h[1]<<endl; else if(op=="DM") { heap_swap(1,cur_size); cur_size--; down(1); } else if(op=="D") { cin>>k; int u=ph[k]; //这里一定要用u=ph[k]保存第k个插入点的下标 heap_swap(u,cur_size); //因为在此处heap_swap操作后ph[k]的值已经发生 cur_size--; //如果在up,down操作中仍然使用ph[k]作为参数就会发生错误 up(u); down(u); } else if(op=="C") { cin>>k>>x; h[ph[k]]=x; //此处由于未涉及heap_swap操作且下面的up、down操作只会发生一个所以 down(ph[k]); //所以可直接传入ph[k]作为参数 up(ph[k]); } } return 0; }
