STL priority_queue 优先级队列

队列 ： 先进先出，按照我们添加元素的顺序来决定
优先级队列 ： 并不是按照元素的添加顺序来访问，而是按照优先级来访问

// 2. 优先级队列存储基本数据类型
void test01()
{
	priority_queue<int> queue1;
	// 用另外一个容器中元素初始化优先级队列
	vector<int> v = { 10, 9, 2, 1, 8 };
	priority_queue<int> queue2(v.begin(), v.end());
}

struct MyCompare
{
	bool operator()(int v1, int v2)
	{
		return v1 < v2;
	}
};

void test02()
{
	// 创建空的优先级队列 : 默认从大到小排序
	// priority_queue<int> q;
	// 设置优先级队列从小到大排序
	// 第一个模板参数：表示的是容器元素的类型
	// 第二个模板参数：实现的底层容器
	// 第三个模板参数：来指定优先级的比较规则
	// priority_queue<int, vector<int>, greater<int>> q;
	// 也可以使用自定义的函数对象来设置模板的第三个参数
	priority_queue<int, vector<int>, MyCompare> q;

	// 向队列中添加元素
	q.push(8);
	q.push(7);
	q.push(4);
	q.push(5);
	q.push(6);

	// 访问优先级队列中的元素
	while (!q.empty())
	{
		// 优先级队列只有一种访问元素的方式，就是谁的优先级高就先访问哪个元素
		// 使用 top 函数返回优先级最高的元素
		cout << q.top() << endl;
		// pop 函数删除优先级最高的元素
		q.pop();
	}

	// 对于基本数据类型，优先级队列按照降序排列规则，将所有的元素进行排序。
	// 所谓的优先级队列内部比普通队列多了一个排序的规则，默认从大到小去访问。
}

// 3. 优先级队列存储自定义类型
class Person
{
public:
	Person(string name, int priority)
	{
		m_name = name;
		m_priority = priority;
	}

#if 0
	bool operator<(const Person& person) const
	{
		return m_priority < person.m_priority;
	}
#endif

public:
	string m_name;
	int m_priority;
};

struct MyComparePerson
{
	bool operator()(const Person& p1, const Person& p2)
	{
		return p1.m_priority < p2.m_priority;
	}
};

struct MyComparePerson2
{
	bool operator()(const Person& p1, const Person& p2)
	{
		return p1.m_priority > p2.m_priority;
	}
};

void test03()
{
	// 1. 给 Person 重载 operator< 函数
	// 2. 给优先级队列的模板参数的第三个参数设置一个能够进行 Person 类型对象比较的函数对象
	// priority_queue<Person, vector<Person>, MyComparePerson> q;

	// 如果希望优先级队列能够根据某个属性从小到大排序
	// 1. 给优先级队列的模板参数指定第三个参数 greater<Person>, 并且在 Person 中重载 operator> 函数
	// 2. 给优先级队列模板的第三个参数指定一个比较函数对象
	priority_queue<Person, vector<Person>, MyComparePerson2> q;


	// 插入元素有两种，第一种创建一个对象存储到容器中，第二种，让容器帮我们构建对象再进行存储
	q.push(Person("smith", 1));
	q.emplace("obama", 7);
	q.emplace("polly", 5);

	while (q.size() > 0)
	{
		// 访问优先最高的人
		const Person& person = q.top();
		cout << person.m_name << " " << person.m_priority << endl;
		// 从队列中删除当前元素
		q.pop();
	}
}