Day1 Heap与Priority_queue
2021/6/21 6:26:15
本文主要是介绍Day1 Heap与Priority_queue,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
Heap
Heap是建立在完全二叉树基础上的一类的特殊的数据结构,主要特征为每个父节点的值都不小于(不大于)其两个子节点的值。
Heap的建立过程本质上是两棵相邻的Heap的合并,只需比较相邻两棵Heap的根和其公共父亲的值的大小关系即可,将最大的值调换到其公共父亲处即可。注意当调换后可能造成被调换的子树不满足Heap性质,需要一路检查到底。
建立完Heap后只要每次取出根节点并将目前最后一个节点调换至根节点并一路交换到底即可。
复杂度\(O(nlogn)\)
代码如下
#include<iostream> #include<cstdio> #define maxn 100050 using namespace std; int n; int a[maxn],b[maxn]; void heap_swap(int x,int size){ while(1){ int ls=x<<1,rs=x<<1|1; if(ls>size)return; if(rs>size){ if(a[x]<a[ls])swap(a[x],a[ls]); return; } if(a[ls]>a[rs]){ if(a[x]<a[ls]){ swap(a[x],a[ls]); x=ls; } else return; } else { if(a[x]<a[rs]){ swap(a[x],a[rs]); x=rs; } else return; } } } void heap_sort(int a[]){ for(int i=n>>1;i;i--) heap_swap(i,n); for(int i=n;i;i--){ b[i]=a[1]; swap(a[1],a[i]); heap_swap(1,i-1); } for(int i=1;i<=n;i++)a[i]=b[i]; } int main(){ cin>>n; for(int i=1;i<=n;i++)cin>>a[i]; heap_sort(a); for(int i=1;i<=n;i++){ cout<<a[i]<<' '; } cout<<endl; }
Priority_queue
基于大根堆和小根堆,我们不难写出一个可以在\(O(logn)\)复杂度内维护数集最大最小值的做法——优先队列。
按照上文的思路,最值便是数组的第一位,删除操作即为取出根节点并将目前最后一个节点调换至根节点并一路交换到底,插入操作即为在最后一位后再插入一个节点并一路向上交换。
代码如下:
#include<iostream> #include<cstdio> #define maxn 100050 using namespace std; int n; void heap_swap(int a[],int x,int size){ while(1){ int ls=x<<1,rs=x<<1|1; if(ls>size)return; if(rs>size){ if(a[x]<a[ls])swap(a[x],a[ls]); return; } if(a[ls]>a[rs]){ if(a[x]<a[ls]){ swap(a[x],a[ls]); x=ls; } else return; } else { if(a[x]<a[rs]){ swap(a[x],a[rs]); x=rs; } else return; } } } struct priority_queue{ int size=0; int x[maxn]; int front(){ return x[1]; } void pop(){ if(!size)return; if(size==1){ size--; return; } swap(x[1],x[size]); size--; heap_swap(x,1,size); } void push(int num){ x[++size]=num; int now=size; while(now){ if(now==1)return; if(x[now]>x[now>>1])swap(x[now],x[now>>1]); else return; } } }; int main(){ /* priority_queue q; q.push(2); q.push(5); q.push(3); q.push(1); cout<<q.front()<<endl; q.pop(); cout<<q.front()<<endl; */ }
这篇关于Day1 Heap与Priority_queue的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-29AutoMQ 产品动态 | 企业版正式上线阿里云、AWS 中国区云市场
- 2024-05-29盘点 AutoMQ 深度使用的阿里云云原生技术
- 2024-05-29盘点 AutoMQ 深度使用的阿里云云原生技术
- 2024-05-29AutoMQ 社区双周精选第十期
- 2024-05-08「布道师系列文章」解析 AutoMQ 对象存储中的文件存储格式
- 2024-05-08「布道师系列文章」小红书黄章衡:AutoMQ Serverless 基石-秒级分区迁移
- 2024-05-08AutoMQ 系统测试体系揭秘
- 2024-03-14AutoMQ 携手阿里云共同发布新一代云原生 Kafka,帮助得物有效压缩 85% Kafka 云支出!
- 2024-02-22kafka partitioner
- 2024-01-24AutoMQ生态集成 - 将数据从 AutoMQ Kafka 导入 RisingWave 数据库