sort和priority_queue比较函数的区别

admin管理员组

文章数量:1623805

• 普通的queue是一种先进先出的数据结构，元素在队列尾追加，而从队列头删除。
• priority_queue中元素被赋予优先级。在创建的时候根据优先级进行了按照从大到小或者从小到大进行了自动排列，。可以以O(log n) 的效率查找一个队列中的最大值或者最小值，其中是最大值还是最小值是根据创建的优先队列的性质来决定的。

两者第三个参数比较函数的区别是相反的。两者默认的都是less

1、less情况

• sort排序是从小到大
• priority_queue是大顶堆，即从大到小

2、greater情况

• sort排序是从大到小
• priority_queue是小顶堆，即从小到大

3、自定义

同样的仿函数，sort和priority_queue也是相反的

struct MyStruct
{
	int data;
	MyStruct(int val)
	{
		data = val;
	}
};

struct cmp {
	bool operator()(const MyStruct& p1, const MyStruct& p2) {
		return p1.data < p2.data;	
	}
};

• sort排序是从小到大
• priority_queue是大顶堆，即从大到小

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>

using namespace std;

struct MyStruct
{
	int data;
	MyStruct(int val)
	{
		data = val;
	}
};
/*自定义比较函数*/
bool sort_cmp(const MyStruct& p1, const MyStruct& p2) {
	return p1.data < p2.data;		// 默认从小到大
}
struct queue_cmp {
	bool operator()(const MyStruct& p1, const MyStruct& p2) {
		return p1.data < p2.data;	// 默认大根堆
	}
};

int main() {
	vector<int> vec{ 4,9,0,2,5 };

	//sort
//  sort(vec.begin(), vec.end());					// 默认从小到大排序,相等于sort(a.begin(), a.end(), less<int>())
	sort(vec.begin(), vec.end(), greater<int>());	// 从大到小排序


	//priority_queue
	//优先级队列，比较函数的作用和 sort 相反
//  priority_queue<int> q;	// 默认大顶堆,相当于priority_queue<int, vector<int>, less<int> >
	priority_queue<int, vector<int>, greater<int> > q;		// 小顶堆

	for (int i = 0; i < vec.size(); i++)
	{
		q.push(vec[i]);
	}

	
	for (int i = 0; i < vec.size(); i++)
	{
		cout << vec[i] << " ";
	}
	cout << endl;
	
	while (!q.empty()) 
	{
		cout << q.top() << " ";
		q.pop();
	}
	cout << endl;


	//自定义
	MyStruct m1(10);
	MyStruct m2(6);
	MyStruct m3(28);
	MyStruct m4(8);
	MyStruct m5(1);

	vector<MyStruct> vec_st;
	vec_st.push_back(m1);
	vec_st.push_back(m2);
	vec_st.push_back(m3);
	vec_st.push_back(m4);
	vec_st.push_back(m5);
	sort(vec_st.begin(), vec_st.end(), sort_cmp);
	for (int i = 0; i < vec_st.size(); i++)
	{
		cout << vec_st[i].data << " ";
	}
	cout << endl;

	priority_queue<MyStruct, vector<MyStruct>, queue_cmp> que;      	
	que.push(m1);
	que.push(m2);
	que.push(m3);
	que.push(m4);
	que.push(m5);
	while (!que.empty())
	{
		cout << que.top().data << " ";
		que.pop();
	}
	cout << endl;
	return 0;
}

本文标签： 函数区别sortpriorityqueue