【CPP】优先级队列

今天来简单分享一下写一个极简版的优先级队列。

1.什么是优先级队列？？？

优先级队列属于STL中队列的一种，虽然包含在队列容器里，但它并不是真正的队列。
在本质上，优先级队列更像一个堆，默认是大堆。
链接：LINK

下面我们简单来认识一下优先级队列的基本使用。

2.优先级队列的基本使用与理解

优先级队列的主要接口有下面这些：

// 优先级队列，默认底层是大堆。
priority_queue<int> ps;
ps.push(2);
ps.push(3);
ps.push(4);
ps.push(1);

while (!ps.empty())
{
	cout << ps.top() << " ";
	ps.pop();
}

那可以让他变成小堆吗？当然可以。但是需要用到仿函数。

// 优先级队列，可以用仿函数置为小堆
priority_queue<int, vector<int>, greater<int>> pq;
pq.push(2);
pq.push(3);
pq.push(4);
pq.push(1);

while (!pq.empty())
{
	cout << pq.top() << " ";
	pq.pop();
}

这里区分两个概念：取出结果是有序与真正排序的区别。
在上面优先级队列中，我们发现while+top取出的数据是有序的，这是因为我们每次取得都是堆顶元素。至于怎么弄的，可以参考C数据结构钟堆删除数据时候得操作，首尾交换，然后size–，我觉得应该是相同的操作。

// 我们发现sort默认排序为升序。
vector<int> v = { 1,3,4,2 };
vector<int>::iterator it = v.begin();
while (it != v.end())
{
	cout << *it << " ";
	it++;
}
cout << endl;

sort(v.begin(), v.end());
it = v.begin();
while (it != v.end())
{
	cout << *it << " ";
	it++;
}

为了让sort变成升序，我们也可以用仿函数进行设置。

vector<int> v = { 1,3,4,2 };
vector<int>::iterator it = v.begin();
while (it != v.end())
{
	cout << *it << " ";
	it++;
}
cout << endl;

sort(v.begin(), v.end(), greater<int>());
it = v.begin();
while (it != v.end())
{
	cout << *it << " ";
	it++;
}

重点区分一个地方：模板参数与函数参数的需要
priority_queue<int, vector<int>, greater<int>> pq;
sort(v.begin(), v.end(), greater<int>());
我们发现两个greater一个带括号一个不带，这是什么情况呢？

要注意优先级队列是一种模板，需要的是类型进行实例化，而sort是模板实例化出来的一种函数，需要迭代器区间和具体的比较仿函数对象，而不是仅仅一个仿函数类型就行。

3.优先级队列的模拟实现

#pragma once
#include<vector>
#include<iostream>
using namespace std;

template<typename T>
struct Less
{
public:
	bool operator()(const T& x, const T& y)
	{
		return x < y;
	}
};

template<typename T>
struct Greater
{
public:
	bool operator()(const T& x, const T& y)
	{
		return x > y;
	}
};

template<class T, class Container = vector<T>, class Compare = Greater<T>>
class periority_queue
{
private:
	Container _con;
public:
	void adjust_up(int child)
	{
		Compare com;
		int parent = (child - 1) / 2;

		while (child > 0)
		{
			if (com(_con[child], _con[parent]))
			{
				swap(_con[child], _con[parent]);
				child = parent;
				parent = (child - 1) / 2;
			}
			else
			{
				break;
			}
		}
	}

	void push(const T& x)
	{
		_con.push_back(x);
		adjust_up(_con.size() - 1);
	}

	void adjust_down(int parent)
	{
		Compare com;
		int child = parent * 2 + 1;
		while (child < _con.size())
		{
			if (child + 1 < _con.size() && com(_con[child + 1], _con[child]))
			{
				child = child + 1;
			}

			if (com(_con[child], _con[parent]))
			{
				swap(_con[child], _con[parent]);
				parent = child;
				child = parent * 2 + 1;
			}
			else
			{
				break;
			}
		}
	}

	void pop()
	{
		swap(_con[0], _con[_con.size() - 1]);
		_con.pop_back();
		adjust_down(0);
	}

	size_t size()
	{
		return _con.size();
	}

	bool empty()
	{
		return _con.empty();
	}

	const T& top()
	{
		return _con[0];
	}
};

其实大部分接口实现都是复用vector的，但是插入和删除接口的逻辑还需要重点看一下。整体没什么难点，需要注意的是我们实现用了一个comper的东西去控制是建小堆/大堆。
comper传的是仿函数类型。我们在向上/向下调整算法中使用这个仿函数类型生成了仿函数(函数对象)进行控制。

引入仿函数的意义：
在本实例中，仿函数是用来控制是建大堆/小堆的，我们C语言可以传函数指针来控制，这个CPP的话比较习惯用仿函数，说白了就是传入一个特殊类对象来控制，感觉无论是C语言的传函数指针还是CPP传仿函数如果控制得当都挺好用，当然前提是C语言那个指针得玩的明白。CPP这个算是一种难度降低吧，毕竟函数指针有时候会弄错。

EOF