C++ STL学习之【优先级队列】-Toy模板网

这篇具有很好参考价值的文章主要介绍了C++ STL学习之【优先级队列】。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

✨个人主页： 北海
🎉所属专栏： C++修行之路
🎃操作环境： Visual Studio 2019 版本 16.11.17

C++ STL学习之【优先级队列】

🌇前言

优先级队列 priority_queue 是容器适配器中的一种，常用来进行对数据进行优先级处理，比如优先级高的值在前面，这其实就是初阶数据结构中的 堆，它俩本质上是一样东西，底层都是以数组存储的完全二叉树，不过优先级队列 priority_queue 中加入了 泛型编程 的思想，并且属于 STL 中的一部分

这就是一个堆，最顶上的石头 优先级最高 或 优先级最低

C++ STL学习之【优先级队列】

🏙️正文

1、优先级队列的使用

首先需要认识一下优先级队列 priority_queue

C++ STL学习之【优先级队列】

1.1、基本功能

优先级队列的构造方式有两种：直接构造一个空对象 和 通过迭代器区间进行构造

C++ STL学习之【优先级队列】
直接构造一个空对象

#include <iostream>
#include <vector>
#include <queue>	//注意：优先级队列包含在 queue 的头文件中

using namespace std;

int main()
{
	priority_queue<int> pq;	//直接构造一个空对象，默认为大堆
	cout << typeid(pq).name() << endl;	//查看类型
	return 0;
}

C++ STL学习之【优先级队列】
注意：默认比较方式为 less，最终为优先级高的值排在上面（大堆）

通过迭代器区间构造对象

#include <iostream>
#include <vector>
#include <queue>	//注意：优先级队列包含在 queue 的头文件中

using namespace std;

int main()
{
	vector<char> vc = { 'a','b','c','d','e' };
	priority_queue<char, deque<char>, greater<char>> pq(vc.begin(), vc.end());	//现在是小堆
	cout << typeid(pq).name() << endl;	//查看类型
	cout << "==========================" << endl;
	while (!pq.empty())
	{
		//将小堆中的堆顶元素，依次打印
		cout << pq.top() << " ";
		pq.pop();
	}
	return 0;
}

C++ STL学习之【优先级队列】
注意：将比较方式改为 greater 后，生成的是 小堆，并且如果想修改比较方式的话，需要指明模板参数2 底层容器，因为比较方式位于模板参数3，不能跳跃缺省（遵循缺省参数规则）

测试数据：27,15,19,18,28,34,65,49,25,37 分别生成大堆与小堆

大堆

vector<int> v = { 27,15,19,18,28,34,65,49,25,37 };
priority_queue<int, vector<int>, less<int>> pq(v.begin(), v.end());
//priority_queue<int> pq(v.begin(), v.end());	//两种写法结果是一样的，默认为大堆

C++ STL学习之【优先级队列】

小堆

vector<int> v = { 27,15,19,18,28,34,65,49,25,37 };
priority_queue<int, vector<int>, greater<int>> pq(v.begin(), v.end());	//生成小堆

C++ STL学习之【优先级队列】

接下来使用优先级队列（以大堆为例）中的各种功能：入堆、出堆、查看堆顶元素、查看堆中元素个数

C++ STL学习之【优先级队列】

#include <iostream>
#include <vector>
#include <queue>	//注意：优先级队列包含在 queue 的头文件中

using namespace std;

void Print(const priority_queue<int>& pq)
{
	cout << "是否为空：" << pq.empty() << endl;
	cout << "堆中的有效元素个数：" << pq.size() << endl;
	cout << "堆顶元素：" << pq.top() << endl;
	cout << "=================" << endl;
}

int main()
{
	vector<int> v = { 27,15,19,18,28,34,65,49,25,37 };
	priority_queue<int> pq(v.begin(), v.end());	//默认生成大堆
	Print(pq);

	pq.push(10);
	pq.push(100);
	Print(pq);

	pq.pop();
	pq.pop();
	pq.pop();
	Print(pq);

	return 0;
}

C++ STL学习之【优先级队列】

1.2、优先级模式切换

创建优先级队列时，默认为 大堆，因为比较方式（仿函数）缺省值为 less，这个设计比较反人类，小于 less 是大堆，大于 greater 是小堆…

如果想要创建 小堆，需要将比较方式（仿函数）改为 greater

注意：因为比较方式（仿函数）位于参数3，而参数2也为缺省参数，因此如果想要修改参数3，就得指明参数2

讲人话就是想改变比较方式的话，需要把参数2也写出来，这个设计也比较反人类，明明只改一个比较方式，为什么要写明底层容器…

priority_queue<int> pqBig;	//大堆
priority_queue<int, vector<int>, greater<int>> pqSmall;	//小堆

1.3、相关题目

优先级队列（堆）可以用来进行排序和解决 Top-K 问题，比如 查找第 k 个最大的值 就比较适合使用优先级队列

215. 数组中的第K个最大元素

C++ STL学习之【优先级队列】

思路：利用数组建立大小为 k 的小堆，将剩余数据与堆顶值比较，如果大于，就入堆

为什么建小堆？因为此时需要的是最大的值，建大堆可能会导致次大的值无法入堆

#include <queue>

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        //建堆
        priority_queue<int, vector<int>, greater<int>> pq(nums.begin(), nums.begin() + k);

        //将剩余元素判断入堆
        auto it = nums.begin() + k;
        while(it != nums.end())
        {
            if(*it > pq.top())
            {
                pq.pop();   //出小的值
                pq.push(*it);   //入大的值
            }

            it++;
        }

        //此时的堆顶元素，就是第 k 个最大元素
        return pq.top();
    }
};

C++ STL学习之【优先级队列】
优先级队列非常适合用来解决类似问题

2、模拟实现优先级队列

优先级队列 priority_queue 属于容器适配器的一种，像栈和队列一样，没有迭代器，同时也不需要实现自己的具体功能，调用底层容器的功能就行了，不过因为堆比较特殊，需要具备 向上调整 和 向下调整 的能力，确保符合堆的规则

2.1、构造函数

注：现在实现的是没有仿函数的版本

优先级队列的基本框架为

#pragma once

#include <vector>

namespace Yohifo
{
	//默认底层结构为 vector
	template<class T, class Container = std::vector<T>>
	class priority_queue
	{
	public:
		//构造函数及其他功能
	private:
		Container _con;	//其中的成员变量为底层容器对象
	};
}

默认构造函数：显式调用底层结构的默认构造函数

//默认构造函数
priority_queue()
	:_con()
{}

迭代器区间构造：将区间进行遍历，逐个插入即可

//迭代器区间构造
template<class InputIterator>
priority_queue(InputIterator first, InputIterator last)
	:_con()
{
	while (first != last)
	{
		push(*first);
		first++;
	}
}

测试：

C++ STL学习之【优先级队列】

2.2、基本功能

因为是容器适配器，所以优先级队列也没有迭代器

同时基本功能也比较少，首先来看看比较简单的容量相关函数

容量相关

判断是否为空：复用底层结构的判空函数

//判断是否为空
bool empty() const
{
	return _con.empty();
}

获取优先级队列大小：复用获取大小的函数

//优先级队列的大小（有效元素数）
size_t size() const
{
	return _con.size();
}

获取堆顶元素：堆顶元素即第一个元素（完全二叉树的根）

//堆顶元素（优先级最 高/低 的值）
const T& top() const
{
	return _con.front();
}

注意：以上三个函数均为涉及对象内容的改变，因此均使用 const 修饰 this 指针所指向的内容

数据修改

因为在插入/删除数据后，需要确保堆能符合要求

大堆：父节点比子节点大
小堆：父节点比子节点小

因此每进行一次数据修改相关操作，都需要检查当前堆结构是否被破坏，这一过程称为调整

插入数据：尾插数据，然后向上调整

//插入数据
void push(const T& val)
{
	//直接尾插，然后向上调整
	_con.push_back(val);
	adjust_up(size() - 1);	//从当前插入的节点处进行调整
}

向上调整：将当前子节点与父节点进行比较，确保符合堆的特性，如果不符合，需要进行调整

//向上调整
void adjust_up(size_t child)
{
	size_t parent = (child - 1) / 2;

	while (child != 0)
	{
		//父 > 子 此时为大堆，如果不符合，则调整
		if (_con[child] > _con[parent])
		{
			std::swap(_con[child], _con[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
			break;
	}
}

注意：如果在调整过程中，发现遵循堆的特性，那么此时不需要再调整，直接 break 即可

删除数据：将堆顶数据交换至堆底，删除堆底元素，再向下调整堆

//删除堆顶元素（优先级最 高/低 的值）
void pop()
{
	if (empty()) 
		return;

	//将堆顶元素交换至堆底删除，向下调整
	std::swap(_con.front(), _con.back());
	_con.pop_back();
	adjust_down(0);
}

向下调整：将当前父节点与【较大 / 较小】子节点进行比较，确保符合堆的特性，如果不符合，需要进行调整

//向下调整
void adjust_down(size_t parent)
{
	size_t child = parent * 2 + 1;	//假设左孩子为 【大孩子 / 小孩子】

	while (child < size())
	{
		//判断右孩子是否比左孩子更符合条件，如果是，则切换为与右孩子进行比较
		if (child + 1 < size() && _con[child + 1] > _con[child])
			child++;

		//父 > 子 此时为大堆，如果不符合，则调整
		if (_con[child] > _con[parent])
		{
			std::swap(_con[child], _con[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
			break;	//满足条件时，一样需要跳出，不再调整
	}
}

注意：删除时，需要先判断当前堆是否为空，空则不执行删除

测试：

C++ STL学习之【优先级队列】

假设先使用 小堆，需要将下图中的三处逻辑判断，改为 <

C++ STL学习之【优先级队列】

难道每次使用时都得手动切换吗？而且如果我想同时使用大堆和小堆时该怎么办？

答案是没必要，通过 仿函数 可以轻松解决问题，这也是本文的重点内容

2.3、仿函数的使用

仿函数又名函数对象 function objects，仿函数的主要作用是 借助类和运算符重载，做到同一格式兼容所有函数 这有点像函数指针，相比于函数指针又长又难理解的定义，仿函数的使用可谓是很简单了

下面是两个仿函数，作用是比较大小

template<class T>
struct less
{
	//比较 是否小于
	bool operator()(const T& x, const T& y)
	{
		return x < y;
	}
};

template<class T>
struct greater
{
	//比较 是否大于
	bool operator()(const T& x, const T& y)
	{
		return x > y;
	}
};

此时 priority_queue 中的模板参数升级为3个，而参数3的缺省值就是 less

template<class T, class Container = std::vector<T>, class Comper = less<T>>

当需要进行逻辑比较时（大小堆需要不同的比较逻辑），只需要调用 operator() 进行比较即可

这里采用的是匿名对象调用的方式，当然也可以直接实例化出一个对象，然后再调用 operator() 进行比较

在使用仿函数后，向上调整 和 向下调整 变成了下面这个样子

//向上调整
void adjust_up(size_t child)
{
	size_t parent = (child - 1) / 2;

	while (child != 0)
	{
		//父 > 子 此时为大堆，如果不符合，则调整
		if (Comper()(_con[parent], _con[child]))	//Comper() 为匿名对象
		{
			std::swap(_con[child], _con[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
			break;
	}
}

//向下调整
void adjust_down(size_t parent)
{
	size_t child = parent * 2 + 1;	//假设左孩子为 【大孩子 / 小孩子】

	while (child < size())
	{
		//判断右孩子是否比左孩子更符合条件，如果是，则切换为与右孩子进行比较
		//同样使用匿名对象
		if (child + 1 < size() && Comper()(_con[child], _con[child + 1]))
			child++;

		//父 > 子 此时为大堆，如果不符合，则调整
		if (Comper()(_con[parent], _con[child]))	//匿名对象调用 operator()
		{
			std::swap(_con[child], _con[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
			break;	//满足条件时，一样需要跳出，不再调整
	}
}

使用仿函数后，可以轻松切换为小堆

C++ STL学习之【优先级队列】

注意：为了避免自己写的仿函数名与库中的仿函数名起冲突，最好加上命令空间，访问指定域中的仿函数

仿函数作为 STL 六大组件之一，处处体现着泛型编程的思想

C++ STL学习之【优先级队列】

仿函数给我们留了很大的发挥空间，只要我们设计的仿函数符合调用规则，那么其中的具体比较内容可以自定义（后续在进行特殊场景的比较时，作用很大）

2.4、特殊场景

假设此时存在 日期类（部分）

class Date

class Date
{
public:
	Date(int year = 1970, int month = 1, int day = 1)
		: _year(year)
		, _month(month)
		, _day(day)
	{}
	bool operator<(const Date& d)const
	{
		return (_year < d._year) ||
			(_year == d._year && _month < d._month) ||
			(_year == d._year && _month == d._month && _day < d._day);
	}
	bool operator>(const Date& d)const
	{
		return (_year > d._year) ||
			(_year == d._year && _month > d._month) ||
			(_year == d._year && _month == d._month && _day > d._day);
	}
	friend std::ostream& operator<<(std::ostream& _cout, const Date& d)
	{
		_cout << d._year << "-" << d._month << "-" << d._day;
		return _cout;
	}
private:
	int _year;
	int _month;
	int _day;
};

创建数据为 Date 的优先级队列（大堆），取堆顶元素（判断是否能对自定义类型进行正确调整）

void TestPriorityQueue3()
{
	Yohifo::priority_queue<Date> q1;
	q1.push(Date(2012, 3, 11));
	q1.push(Date(2012, 3, 12));
	q1.push(Date(2012, 3, 13));
	cout << q1.top() << endl;	//取堆顶元素
}

结果：正确，因为在实际比较时，调用的是 Date 自己的比较逻辑，所以没问题

C++ STL学习之【优先级队列】

但如果此时数据为 Date*，再进行比较

void TestPriorityQueue4()
{
	//数据类型为指针
	Yohifo::priority_queue<Date*> q1·;
	q1.push(new Date(2012, 3, 11));
	q1.push(new Date(2012, 3, 12));
	q1.push(new Date(2012, 3, 13));
	cout << *(q1.top()) << endl;
}

结果：错误，多次运行结果不一样！因为此时调用的是指针的比较逻辑（地址是随机的，因此结果也是随机的）

C++ STL学习之【优先级队列】
解决方法：

通过再编写指针的仿函数解决
通过模板特化解决

这里介绍法1，法2在下篇文章《模板进阶》中讲解

仿函数给我们提供了极高的自由度，因此可以专门为 Date* 编写一个仿函数（曲线救国）

//小于
template<class T>
struct pDateLess
{
	bool operator()(const T& p1, const T& p2)
	{
		return (*p1) < (*p2);
	}
};

//大于
template<class T>
struct pDateGreater
{
	bool operator()(const T& p1, const T& p2)
	{
		return (*p1) > (*p2);
	}
};

在构建对象时，带上对对应的 仿函数 就行了

void TestPriorityQueue5()
{
	//数据类型为指针
	Yohifo::priority_queue<Date*, vector<Date*>, pDateLess<Date*>> qBig;
	qBig.push(new Date(2012, 3, 11));
	qBig.push(new Date(2012, 3, 12));
	qBig.push(new Date(2012, 3, 13));
	cout << *(qBig.top()) << endl;

	Yohifo::priority_queue<Date*, vector<Date*>, pDateGreater<Date*>> qSmall;
	qSmall.push(new Date(2012, 3, 11));
	qSmall.push(new Date(2012, 3, 12));
	qSmall.push(new Date(2012, 3, 13));
	cout << *(qSmall.top()) << endl;
}

此时无论是大堆还是小堆都能进行正常比较

C++ STL学习之【优先级队列】

关于 Date* 仿函数的具体调用过程，可以自己下去通过调试观察

3、源码

本文中提及的所有源码都在此仓库中 《优先级队列博客》

C++ STL学习之【优先级队列】

🌆总结

以上就是本次关于 C++ STL学习之【优先级队列】的全部内容了，在本文中，我们又学习了一种容器适配器 priority_queue，优先级队列在对大量数据进行 Top-K 筛选时，优势是非常明显的，因此需要好好学习，尤其是向上调整和向下调整这两个重点函数；最后我们还见识了仿函数的强大之处，容器在搭配仿函数后，能做到更加灵活，适应更多需求

C++ STL学习之【优先级队列】

文章来源地址https://www.toymoban.com/news/detail-447162.html
相关文章推荐
STL 之适配器
C++ STL学习之【反向迭代器】
C++ STL学习之【容器适配器】 ===============
STL 之 list
C++ STL学习之【list的模拟实现】
C++ STL学习之【list的使用】 ===============
STL 之 vector
C++ STL学习之【vector的模拟实现】
C++ STL学习之【vector的使用】