网站浮动窗口代码,html网页生成,哪里有响应式网站企业,环球军事网最新军事新闻目录 引言一、最小堆概念二、堆排序模板#xff08;最小堆#xff09;三、模拟堆 引言
这个堆排序的话#xff0c;考的还挺多的#xff0c;主要是构建最小堆#xff0c;并且在很多情况下某些东西还用得着它来优化#xff0c;比如说迪杰斯特拉算法可以用最小堆优化#… 目录 引言一、最小堆概念二、堆排序模板最小堆三、模拟堆 引言
这个堆排序的话考的还挺多的主要是构建最小堆并且在很多情况下某些东西还用得着它来优化比如说迪杰斯特拉算法可以用最小堆优化然后面试和考研用的也是挺多的总之开始吧。
一、最小堆概念
本文只讲述最小堆其一这个用的最多而且跟最大堆来说其实都是差不多的就一个小于一个大于
最小堆首先是一个完全二叉树然后每个结点都小于或等于其两个儿子性质根结点是整个堆的最小值。因为父亲是最小的然后儿子又作为其儿子的父亲也是其最小的所以推出堆根是最小的。
存储方式是用数组来存的i 号下标的儿子为 2 * i2 * i 1i 号下标的父亲为 i / 2
STL优先级队列就是最小堆
二、堆排序模板最小堆
整体思路先构建一个最小堆然后输出堆根再把堆根删了再次构建重复往返 删除堆根用 h[size] 覆盖 h[1] ,size-- down(1) 这个模板我们用例题来说明
输入一个长度为 n 的整数数列从小到大输出前 m 小的数。输入格式
第一行包含整数 n 和 m。
第二行包含 n 个整数表示整数数列。输出格式
共一行包含 m 个整数表示整数数列中前 m 小的数。数据范围
1≤m≤n≤1051≤数列中元素≤109输入样例
5 3
4 5 1 3 2输出样例
1 2 3#include cstdio
#include cstring
#include iostreamusing namespace std;const int N 1e510;int h[N]; //h[i]代表第堆中的i号下标对应的值
int n, m, cnt; //cnt代表堆中的数量//元素变小了就up
void up(int u)
{while(u / 2 h[u / 2] h[u]) //若u1 并且比父亲大就交换然后u变成父亲继续判断{swap(h[u], h[u/2]);u 1;}
}//元素变大了就down
void down(int u) //将下标为u的元素下移
{int t u;if(u * 2 cnt h[2 * u] h[t]) t 2 * u; if(u * 2 1 cnt h[2 * u 1] h[t]) t 2 * u 1; //判断最小的值tif(t ! u) //若有一个儿子比自己小{swap(h[u], h[t]); //交换值down(t); //再次判断这个儿子}
}int main()
{scanf(%d%d, n, m);for(int i 1; i n; i) scanf(%d, h[i]);cnt n;for(int i cnt / 2; i; --i) down(i); //从倒数第二层的元素开始down到根可以构建一个最小堆while(m--){printf(%d , h[1]); //每次都是堆根的元素最小swap(h[1], h[cnt]);cnt--;down(1);}return 0;
}三、模拟堆
我们还是用例题来说明 然后这个有一个要求就是要对第k个插入的元素进行操作但是我们又不知道第k个元素是谁只知道下标所以得维护两个数组ph[i] hp[i]代表ph[k] ihp[i] kh[i] a
维护一个集合初始时集合为空支持如下几种操作
I x插入一个数 x
PM输出当前集合中的最小值
DM删除当前集合中的最小值数据保证此时的最小值唯一
D k删除第 k 个插入的数
C k x修改第 k 个插入的数将其变为 x现在要进行 N 次操作对于所有第 2 个操作输出当前集合的最小值。输入格式
第一行包含整数 N。
接下来 N 行每行包含一个操作指令操作指令为 I xPMDMD k 或 C k x 中的一种。输出格式
对于每个输出指令 PM输出一个结果表示当前集合中的最小值。每个结果占一行。数据范围
1≤N≤105
−109≤x≤109
数据保证合法。输入样例
8
I -10
PM
I -10
D 1
C 2 8
I 6
PM
DM输出样例
-10
6#include cstdio
#include cstring
#include iostreamusing namespace std;const int N 1e510;int h[N], hp[N], ph[N];
int n, cnt, idx;void swap_heap(int a, int b)
{swap(ph[hp[a]],ph[hp[b]]);swap(hp[a],hp[b]);swap(h[a], h[b]);
}void up(int u)
{while(u / 2 h[u] h[u / 2]){swap_heap(u, u/2);u 1;}
}void down(int u)
{int t u;if(u * 2 cnt h[u * 2] h[t]) t u * 2;if(u * 2 1 cnt h[u * 2 1] h[t]) t u * 2 1;if(t ! u){swap_heap(t,u);down(t);}
}int main()
{scanf(%d, n);while(n--){char op[5];int k, x;scanf(%s, op);if(!strcmp(op,I)){scanf(%d, x);cnt, idx;h[cnt] x;hp[cnt] idx, ph[idx] cnt;up(cnt);}else if(!strcmp(op,PM)){printf(%d\n, h[1]);}else if(!strcmp(op,DM)){swap_heap(1,cnt);cnt--;down(1);}else if(!strcmp(op,D)){scanf(%d, k);k ph[k];swap_heap(k, cnt);cnt--;up(k);down(k);}else{scanf(%d%d, k, x);k ph[k];h[k] x;up(k);down(k);}}return 0;
}
