基础算法学习--堆的模拟
2021/4/24 20:25:33
本文主要是介绍基础算法学习--堆的模拟,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
什么是堆?
- 一颗完全二叉树,根是整棵树的最小值
- 每一层的子节点都大于对应根节点
堆的模板(不考虑数是第几个插入的)
int h[N]; //value int idx; //树的大小 //将当前的数向下排序 void down(int num){ int t = num; if(num * 2 <= idx && h[num * 2 ] < h[t]) t = num * 2; if(num * 2 + 1 <= idx && h[num * 2 + 1] < h[t]) t = num * 2 + 1; if(t != num){ swap(h[t],h[num]); down(t); } } //将当前的数向上排序 void up(int num){ if(num >> 1 && h[num] < h[num >> 1]){ swap(h[num],h[num >> 1]); up(num >> 1); } } //将n个数据初始化成一个堆。 for(int i = 1;i <= n;i ++) cin >> h[i]; idx = n; //从倒数第二层开始做down for(int i = n >> 1;i;i --) down(i); //插入操作 void ins(int num){ idx ++; h[idx] = num; down(idx),up(idx); //up和down最多只会执行一个,所以不考虑下标变换 } //删除最小值 void del(){ swap(h[1],h[idx]); idx --; down(1); }
也是模板(考虑是第几个插入的)
//h存的是value,hp存的是idx映射的cnt,ph存的是cnt映射的idx,idx为树里的下标,cnt为插入的序号 int h[N],hp[N],ph[N]; int cnt; int idx; //头部交换 void head_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 num){ int t = num; if(num * 2 <= idx && h[num * 2] < h[t]) t = num * 2; if(num * 2 + 1 <= idx && h[num * 2 + 1] < h[t]) t = num * 2 + 1; if(t != num){ head_swap(t,num); down(t); } } //往上排序 void up(int num){ if(num / 2 && h[num / 2] > h[num]){ head_swap(num,num / 2); up(num / 2); } } //插入一个数 void ins(int a){ idx ++; //堆里面有几个数 cnt ++; //第k个插入的数 //映射 ph[cnt] = idx; hp[idx] = cnt; h[idx] = a; up(idx); } //删除第k个插入的数 void del_k(int a){ //一定要注意保留原来指向的值,不然会在后面的swap里被改变 a = ph[a]; head_swap(a,idx); idx --; down(a),up(a); //down和up可能都会执行 } //将第k个插入的数的值改成b void change_k(int a,int b){ //一定要注意保留原来指向的值,不然会在后面的swap里被改变 a = ph[a]; h[a] = b; down(a),up(a); //down和up可能都会执行 }
模拟堆
#include<iostream> #include<cstring> using namespace std; const int N = 100010; //h存的是value,hp存的是idx映射的cnt,ph存的是cnt映射的idx,idx为树里的下标,cnt为插入的序号 int h[N],hp[N],ph[N]; int cnt; int idx; //头部交换 void head_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 num){ int t = num; if(num * 2 <= idx && h[num * 2] < h[t]) t = num * 2; if(num * 2 + 1 <= idx && h[num * 2 + 1] < h[t]) t = num * 2 + 1; if(t != num){ head_swap(t,num); down(t); } } //往上排序 void up(int num){ if(num / 2 && h[num / 2] > h[num]){ head_swap(num,num / 2); up(num / 2); } } int main(){ int n; cin >> n; while(n --){ int a,b; char op[10]; scanf("%s",op); if(!strcmp(op,"I")){ cin >> a; idx ++; cnt ++; ph[cnt] = idx; hp[idx] = cnt; h[idx] = a; up(idx); }else if(!strcmp(op,"PM")) cout << h[1] << endl; else if(!strcmp(op,"DM")){ head_swap(1,idx); idx --; down(1); }else if(!strcmp(op,"C")){ cin >> a >> b; //一定要注意保留原来指向的值,不然会在后面的swap里被改变 a = ph[a]; h[a] = b; down(a); up(a); }else{ cin >> a; //一定要注意保留原来指向的值,不然会在后面的swap里被改变 a = ph[a]; head_swap(a,idx); idx --; down(a); up(a); } } return 0; }
这篇关于基础算法学习--堆的模拟的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-28微服务架构中API版本控制的实践
- 2024-09-28AI给的和自己写的Python代码,都无法改变输入框的内容,替换也不行
- 2024-09-27Sentinel配置限流资料:新手入门教程
- 2024-09-27Sentinel配置限流资料详解
- 2024-09-27Sentinel限流资料:新手入门教程
- 2024-09-26Sentinel限流资料入门详解
- 2024-09-26Springboot框架资料:初学者入门教程
- 2024-09-26Springboot框架资料详解:新手入门教程
- 2024-09-26Springboot企业级开发资料:新手入门指南
- 2024-09-26SpringBoot企业级开发资料新手指南