数据结构&堆&heap&priority_queue&实现
程序员文章站
2022-08-28 11:07:06
[toc] 什么是堆? 堆是一种数据结构,可以用来实现优先队列 大根堆 大根堆,顾名思义就是根节点最大。我们先用小根堆的建堆过程学习堆的思想。 小根堆 下图为小根堆建堆过程 堆的操作 上浮 下沉 插入 弹出 取顶 堆排序 STL heap 所在库 include cpp include using ......
目录
什么是堆?
堆是一种数据结构,可以用来实现优先队列
大根堆
大根堆,顾名思义就是根节点最大。我们先用小根堆的建堆过程学习堆的思想。
小根堆
下图为小根堆建堆过程
堆的操作
- 上浮
- 下沉
- 插入
- 弹出
- 取顶
-
堆排序
stl heap
所在库 #include
#include<cstdio> #include<iostream> #include<algorithm> #include<vector> using namespace std; bool cmp(int x,int y) { return x>y; } int main() { vector<int> a; int num,n=10; for(int i=0;i<n;i++) { num = rand()%(233*2); a.push_back(num); } for(vector<int>::iterator i=a.begin();i!=a.end();i++) { cout<<*i<<ends; }cout<<endl<<endl; make_heap(a.begin(),a.end());//默认的大根堆 for(vector<int>::iterator i=a.begin();i!=a.end();i++) { cout<<*i<<ends; }cout<<endl<<endl; make_heap(a.begin(),a.end(),cmp);//自制的小根堆 for(vector<int>::iterator i=a.begin();i!=a.end();i++) { cout<<*i<<ends; }cout<<endl<<endl; a.push_back(2333); push_heap(a.begin(),a.end(),cmp);//将新加的元素加入堆中 for(vector<int>::iterator i=a.begin();i!=a.end();i++) { cout<<*i<<ends; }cout<<endl<<endl; a.pop_back(); //删除尾部 for(vector<int>::iterator i=a.begin();i!=a.end();i++) { cout<<*i<<ends; }cout<<endl<<endl; getchar();getchar();getchar();getchar(); return 0; }
stl queue
所在库#include
#include<bits/stdc++.h> using namespace std; struct student{ int grade; string name; }; struct cmp{ bool operator() (student s1,student s2){ return s1.grade < s2.grade; } }; int main(int argc, char const *argv[]) { int n=10,num; /* 1. push 【入队插到队尾】 2. pop 【队首元素出队】 3. size 【返回队列中元素的个数】 4. front 【返回队列中第一个元素】 5. back 【返回队列中最后一个元素】 6. empty 【判断队列是否为空】 */ //cout<<"队列:"<<endl; queue<int> a; for(int i=1;i<n;i++){ num = rand()%233; a.push(num); } //数列长度 cout<<a.size()<<endl; //数列头元素 cout<<a.front()<<endl; //数列尾元素 cout<<a.back()<<endl; //数列是否为空 while(!a.empty()){ cout<<a.front()<<ends; a.pop(); }cout<<endl<<endl; priority_queue<int> pq_1; for(int i=1;i<n;i++){ num = rand()%233; pq_1.push(num); } //默认情况下,数值大的在队首位置(降序) while(!pq_1.empty()){ //注意这里的访问头元素为.top cout<<pq_1.top()<<ends; pq_1.pop(); }cout<<endl; //以下情况下,数值小的在队首位置(升序) priority_queue<int,vector<int>,greater<int> > pq_2; for(int i=1;i<n;i++){ num = rand()%233; pq_2.push(num); } while(!pq_2.empty()){ //注意这里的访问头元素为.top cout<<pq_2.top()<<ends; pq_2.pop(); }cout<<endl;cout<<endl; //运算符重载 priority_queue<student,vector<student>,cmp> q; student s1,s2,s3; s1.grade = 90; s1.name = "tom"; s2.grade = 80; s2.name = "jerry"; s3.grade = 100; s3.name = "kevin"; q.push(s1); q.push(s2); q.push(s3); while(!q.empty()){ cout<<q.top().name<<":"<<q.top().grade<<endl; q.pop(); } getchar(); return 0; }
上一篇: 学习python的前途 python挣钱
下一篇: NOIP 2000 计算器的改良