优先队列(priority_queue)小根堆、大根堆

admin管理员组

文章数量:1623788

• top 访问队头元素
• empty 队列是否为空
• size 返回队列内元素个数
• push 插入元素到队尾 (并排序)
• emplace 原地构造一个元素并插入队列
• pop 弹出队头元素
• swap 交换内容

#include <iostream>
#include <string>
#include<vector>
#include<map>
#include<queue>
#include<unordered_set>
#include<algorithm>
#include<stack> 
using namespace std;
struct cmp1{ // 与普通的比较函数重载相反
	bool operator()(const pair<int,int>&a,const pair<int,int>&b){
		return a.second > b.second; //[1] > [2] 就是愈来愈大
									//[1] < [2] 就是愈来愈小 
	}
};

struct cmp2{
	bool operator()(const int a,const int b){
		return a < b;
	}
};

int main(){
//优先队列大根堆
//priority_queue<type,保存数据容器,排序方式> 
//type就是要处理的是什么数据类型的。比如优先队列内放的是int型，那就是int。if是pair型，那就是pair<int,int>
//保存数据容器就是：用什么容器来存放，据了解一般用vector,if int型:vector<int>。if pair型：vector<pair<int,int>>
//排序方式:如果type是int 或者 string的固有类型可以用less<int>（大根堆）或者greater<int>(小)。如果type是结构
//或者map等，就得重写排序。 
	priority_queue<int,vector<int>,less<int> >a; //标准定义方式
	priority_queue<int> b; // 后面两个参数不写，默认就是大根堆 
	priority_queue<int,vector<int>,greater<int> >c; //小根堆
	for(int i = 0;i < 3;i++){
		a.push(i);
		b.push(i);
		c.push(i);
	} 
	while(!a.empty()){ //输入0 1 2;结果 2 1 0 
		cout << a.top()<<endl;
		a.pop();
	}
	while(!b.empty()){ //输入0 1 2;结果 2 1 0 
		cout << b.top()<<endl;
		b.pop();
	}
	while(!c.empty()){ //输入0 1 2;结果0 1 2 
		cout << c.top()<<endl;
		c.pop();
	}
	
	//2、pair的比较或者结构体等
	priority_queue<pair<int, int> > aa;
	pair<int, int> bb(1, 2);
	pair<int, int> cc(1, 3);
	pair<int, int> dd(2, 5);
	aa.push(dd); //或者make_pair(dd) 
	aa.push(cc);
	aa.push(bb);
	while (!aa.empty()) 
	{
	    cout << aa.top().first << ' ' << aa.top().second << '\n';
	    aa.pop();
	}
	cout << endl;
	
	//自定义优先级,重写比较函数
	// int 或者string 。自定义降序 
	priority_queue<int,vector<int>,cmp2> aaa;
	aaa.push(20);
	aaa.push(100);
	aaa.push(9);
	while(!aaa.empty()){
		cout << aaa.top()<<endl;
		aaa.pop();
	} // 100 20 9
	cout << endl;
	
	//举例pair 
	priority_queue<pair<int,int>,vector<pair<int,int>>,less<pair<int,int>>> e;
	e.push(dd);
	e.push(cc);
	e.push(bb);
	while (!e.empty()) 
	{
	    cout << e.top().first << ' ' << e.top().second << '\n';
	    e.pop();
	}
	return 0;
}

本文标签： 队列priorityqueue大根堆小根堆