目录

前言

priority_queue的使用

功能解析

基本接口

写点题目

模拟实现

结构解析

插入删除

调整函数结合仿函数

仿函数介绍

结合使用

其他功能

接口补齐

迭代器区间构造

前言

?打开 queue 头文件后，我们发现除了我们之前介绍过的普通队列以外，还有一个 priority_queue。

?其又名为优先级队列，之所以叫这个名字正是因为这个队列出队时会根据某种优先级弹出元素。

?听到这个功能是不是觉得有点耳熟，这不就跟我们以前写过的堆一模一样吗？实际上便可以将其当作是库中封装的堆，同时配合模板使其具有更多的自由度。

priority_queue的使用

功能解析

在使用 priority_queue 之前，我们先看一下文档中的内容，模板中有三个参数，分别是内置数据类型、内置容器和仿函数。

?后面两个参数默认有缺省值，直接使用缺省值便是使用 vector 适配构建一个大堆。

[注意] 这里的内置容器可以使用vector和deque，不能使用list。

int main()
{
	priority_queue<int> pq1;    //内部数据类型为int,数据类型为vector,构建大堆
	priority_queue<int, deque<int>> pq2; //内部数据类型为int,数据类型为deque,构建大堆
	priority_queue<int, vector<int>, greater<int>> pq3; //内部数据类型为int,数据类型为vector,构建小堆
	return 0;
}

基本接口

?接口的命名方式与 stack 和 queue 接近，访问第一个元素是 top 而不是 front 不要和 queue 记混了。

?下面通过实例代码简单使用一下：

int main()
{
	priority_queue<int> pq;    //内部数据类型为int,数据类型为vector,构建大堆
	pq.push(1);    //插入数据
	pq.push(0);
	pq.push(5);
	pq.push(2);
	pq.push(1);
	pq.push(7);

	while (!pq.empty())   //直到堆为空之前循环
	{
		cout << pq.top() << " ";  //打印堆顶
		pq.pop();     //弹出元素
	}
	return 0;
}

?之后就是根据从大到小的顺序进行输出。 

?现在我们使用迭代器区间构造小堆，最后输出的结果便是从小到大的。

int main()
{
	int a[] = { 5,4,8,2,5,7,3,9 };
	priority_queue<int, vector<int>, greater<int>> pq(a, a + 8); //使用迭代器区间构造

	while (!pq.empty())   //直到堆为空之前循环
	{
		cout << pq.top() << " ";  //打印堆顶
		pq.pop();     //弹出元素
	}
	return 0;
}

写点题目

?又得将我们 Kvalue 这个题目拎出来了，以前写的时候我们还要自己手搓一个堆出来，今非昔比，我们可以直接使用库里的堆了。

?要求出第大 k 的值，那我们不妨维护一个 k 个值的堆，让数组之后的每一个值都与堆顶元素进行对比，只有比堆顶元素大的元素才插入。同时，为了维护这个效果堆顶元素必须使整个堆中最小的那个元素，因此构建小堆。遍历完整个数组后，堆顶元素就是我们要求的目标值。

int findKthLargest(vector<int>& nums, int k) {
    priority_queue<int, vector<int>, greater<int>> pq(nums.begin(),nums.begin()+k);   //以数组前k个值构建小堆
    for (int i = k; i < nums.size(); i++)   //遍历数组
    {
        int t = pq.top();  
        if(nums[i]>t)      //比堆顶元素大先删除原堆顶元素，再插入
        {
            pq.pop();
            pq.push(nums[i]);
        }
    }
    return pq.top();
}

模拟实现

?priority_queue 的模拟实现本质上就是借助仿函数和模板对堆进行封装，与之前的讲解侧重点可能不同。

?更多细节可以去这里复习一下，堆及堆排序的实现。

结构解析

?根据模板参数定义内置容器和仿函数的对象，而仿函数在下面会进行讲解。

namespace Alpaca
{
    template<class T,class Container = vector<T>,class Compare = less<T>>
	class priority_queue
	{
	public:
    private:
		Container _con;     //内置容器
		Compare com;        //仿函数
	};
}

插入删除

?在之前实现堆的时候，插入和删除的操作都是在数组尾部进行的。

?插入时就直接插入到数组尾，之后再向上调整，而删除需要将堆顶的数据交换到数组尾部，再进行删除，同时，交换上去的那个数需要进行向下调整。

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

void pop()
{
	std::swap(_con[0], _con.back());
	_con.pop_back();
	adjust_down(0);
}

调整函数结合仿函数

仿函数介绍

?在讲这部分之前先简单介绍一下仿函数，我们在一个类中只进行 ( ) 运算符重载，这之后我们便可以像使用函数一样使用这个类。

?如下，我实现一个仿函数用于判断两个值的大小。

struct judge     //直接使用struct定义类使成员函数默认为共有访问的
{
	bool operator ()(const int x, const int y)
	{
		return x > y;
	}
};

int main()
{
	int a = 8, b = 7;
	judge jud;                      //实例化对象
	cout << jud(a, b) << endl;
	cout << judge()(a, b) << endl;  //使用匿名对象
	return 0;
}

?实际上便于函数指针相像，但使用起来会相较函数指针更加简单一些。

?之前我们写堆的时候一次只能写一份，构建的大堆小堆也是写死的，使用了仿函数后便可以将生成的选项交给使用者选择。

?将调整函数与仿函数结合起来就是接下来我们关注的重点。

结合使用

?一个值在数组尾插入后需要根据优先级在堆中找到其对应的位置，因此要进行向上调整，但在以前构建大堆还是小堆是我们在写的时候直接写死的，这里我们就要结合仿函数进行实现。于是在判断时我们便可直接沿用仿函数的返回值，而仿函数的选择由用户决定。

?这样便可由用户自主决定构建出来的是大堆还是小堆，高自由度的同时还能够支持自定义类型的比较(仿函数也可以由用户构建)。

template<class T>    //沿用了库中仿函数的命名规则
struct greater
{
	bool operator ()(const T& x, const T& y)
	{
    	return x > y;
	}
};

template<class T>
struct less
{
	bool operator ()(const T& x, const T& y)
	{
		return x < y;
	}
};

?自己实现仿函数后便可以将其带入到调整函数中去了，同时由于我们在成员变量中定义对象了，因此这里直接使用即可。

void adjust_up(int child)
{
	int parent = (child - 1) / 2;               //向上找父亲
	while (child > 0)
	{
		if (com(_con[parent], _con[child]))     //判断是否符合优先级
		{
			std::swap(_con[child], _con[parent]);   //符合就向上调整，否则结束调整
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

void adjust_down(int parent)
{
	int child = parent * 2 + 1;                //找孩子
	while (child < _con.size())
    {
	    if (child + 1 < _con.size() &&
			com(_con[child], _con[child + 1]))  //根据优先级找最符合的还在
		{
			child++;
		}

		if (com(_con[parent], _con[child]))      //判断是否符合优先级
		{
			std::swap(_con[parent], _con[child]);  //符合则交换
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

其他功能

接口补齐

?之后将剩余的接口补齐即可，分别是堆顶元素、堆的大小、判空和交换。

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

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

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

void swap(priority_queue& pq)
{
	_con.swap(pq._con);
}

迭代器区间构造

?在看文档的时候，还看到通过迭代器区间进行构造，于是便简单实现一下，同时还要写一个无参的默认构造函数。

priority_queue()
{}

template<class interator>
priority_queue(interator begin, interator end)  //迭代器区间构造
{
	while (begin != end)
	{
		push(*begin);            //将每个值push进堆中
		begin++;
	}
}

?好了，今天 priority_queue基本使用和模拟实现 的相关内容到这里就结束了，如果这篇文章对你有用的话还请留下你的三连加关注。