Cpp::STL—容器适配器priority_queue的讲解和模拟实现(17)

文章目录

前言
一、优先级队列的使用
- 介绍
- 使用
- 一道题目
二、仿函数的讲解
- 对内置类型
- 对自定义类型
三、模拟实现priority_queue
- 两个仿函数
- 构造函数
- 向上调整和向下调整
- 插入数据和删除数据
- 其他常用接口
- 总概一览
总结

前言

承接上一篇容器适配器的内容，本篇我们再来学一个优先级队列！
学习它需要我们对之前的堆的内容有一个较为全面的掌握，如果你不是很有信心的话，我建议你回去看看
正文开始！

一、优先级队列的使用

介绍

在这里插入图片描述
我们需要对其有一个这样的认识：

优先队列是一个容器适配器，根据严格的弱排序标准，它的第一个元素总是它所含的元素中最大的
此上下文类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素(优先队列中位于顶部的元素)
优先级队列已经不能称为队列，不符合FIFO特性拉
优先队列被实现为容器适配器，容器适配器即将特定的容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素，元素从特定容器的"尾部"弹出，其称为优先队列的顶部
底层容器可以是任何标准容器类模板，也可以是特定设计的容器类，容器应该可以通过随机访问迭代器访问，并支持以下操作：
empty():检测容器是否为空
size():返回容器中有效元素个数
front():返回容器中第一个元素的引用
push_back():在容器尾部插入元素
pop_back():删除容器尾部元素
标准容器类vector和deque满足这些需求。默认情况下，如果没有为特定的priority_queue类实例化指定容器类，则使用vector
需要支持随机访问迭代器，以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_head,push_heap和pop_heap来自动完成此操作

我们来看看它的三个模板参数，第二个代表底层存储数据的容器，默认为vector，第三个就厉害了，这叫做仿函数（其实就是一个专门用作比较大小的类，我们后面会讲）

第二个容器必须支持随机访问迭代器（Random Access Iterator），以及 front()，push_back()，pop_back() 的操作

使用

优先级队列默认使用vector作为其底层存储数据的容器，在vector上又使用了堆算法将vector中元素构造成堆的结构，因此priority_queue就是堆，所有需要用到堆的位置，都可以考虑使用priority_queue

默认情况下，priority_queue用到的是大堆

#include <iostream>
#include <queue>
using namespace std;
 
int main()
{
	//默认less 大堆
	//如果要改建立小堆也很简单，第三个参数设置为greater<int>
	priority_queue<int> pq;//实例化堆
	pq.push(1);//插入值
	pq.push(4);
	pq.push(2);
	pq.push(3);
 
	//堆不为空时打印堆顶元素，大堆打印出来为降序
	while (!pq.empty())
	{
		cout << pq.top() << " ";//打印堆顶元素
		pq.pop();//删除堆顶元素
	}
	cout << endl;
	
	return 0;
}

构造方式有两种，一种是直接构造一个空对象，另一种是通过迭代器区间去构造
在这里插入图片描述

一道题目

我们之前就说过，堆这种数据结构很适合处理TopK问题，比如说现在给你一个数组 nums 和大小 k ，请帮我求出这个数组第k大的数，你有没有什么思路？

答案是首先先建立一个大小为k的小堆（注意是小堆！！），那么堆顶元素必定是这k个数最小的，现在再把数组剩下的元素走一遍，如果比堆顶元素大，就pop一下，push新数据，这样走完后，小堆里的k个数必定是这个数组里面最大的k个数，而堆顶又是这k个数中最小的那个，即第k大数

力扣215.数组中的第k个最大元素
去试试吧！~

二、仿函数的讲解

对内置类型

仿函数是通过类中运算符重载()实现特定的功能，通过使用匿名对象使用，它的对象可以想函数一样去使用，使得很难区分是调用函数还是调用匿名对象

你可以顾名思义一下，仿函数就是用对象来模仿函数的一种方式，通过类来实现

// 定义一个仿函数模板类
template<class T>
struct Less
{
    // 重载函数调用操作符
	bool operator()(const T& x, const T& y)
	{
		return x < y;
	}
};
 
int main()
{
	Less<int> lessfunc;//创建有名对象
	cout << lessfunc(1, 2) << endl;//有名对象调用类成员函数
	cout << lessfunc.operator()(1, 2) << endl;//显示调用
	cout << Less<int>()(1, 2) << endl;//匿名对象，前面一个括号构造对象，后面调用函数
	cout << Less<int>().operator()(1, 2) << endl;
	
	return 0;
}

我们定义了一个名为 Less 的仿函数类，它重载了 operator() 来实现前面一个数是否小于后面一个数的功能

仿函数广泛用于C++标准库中，特别是在算法（std::sort）中作为比较函数或者操作函数，以及在容器（如 std::set 或者 std::map）中作为排序准则
在这里插入图片描述

仿函数的一个主要优点是它们可以保持状态，这意味着它们可以在多次调用之间保存和修改信息。这使得它们非常灵活和强大。此外，由于它们是类的实例，它们也可以拥有额外的方法和属性

对自定义类型

假设现在有个日期类

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 的优先级队列（大堆），取堆顶元素（判断是否能对自定义类型进行正确调整）
在这里插入图片描述
我们发现这是没问题的，因为在实际比较时，调用的是 Date 自己的比较逻辑

但是问题是我们经常存放的不是自定义类型，而是自定义类型的指针，这时候还能正常比较吗
在这里插入图片描述
答案是不行的，因为此时调用的是指针的比较逻辑，而指针所存储的地址是比较随机的，这时候一共有两种方法，一种是我们下篇要学的模板特化，一种就是专门为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);
	}
};

在这里插入图片描述

成功解决，很神奇吧！

三、模拟实现priority_queue

既然已经对优先级队列有了个大致的认识，不如我们再来好好实现一下它，对它有个更底层的认识！

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

向上调整和向下调整都是实现的一个难点，且为了避免与库里面的优先级队列冲突，我们把它封装到自己的命名空间里面

两个仿函数

明白了仿函数的概念和意义后，应该可以很自然的写出两种仿函数，并且我们要访问内部函数，干脆直接 struct 就行

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

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

构造函数

因为有两种，一种用迭代器，一种为空，迭代器会覆盖掉默认的构造参数，我们这里借助default来强制生成默认构造函数

	template<class T, class Container = vector<T>, class Compare = Myless<T>>
	class priority_queue
	{
	public:
		priority_queue() = default;

		template<class InputIterator>
		priority_queue(InputIterator first, InputIterator last)
		{
			// 1.把数据全部存放到存储数据的容器中
			while (first != last) {
				_con.push_back(*first);
				++first;
			}
			// 2.向下调整建堆，默认为大堆
			for (int i = (_con.size() - 2) / 2; i >= 0; i--) {
				adjust_down(i);
			}
		}
	private:
		Container _con;
	};

向上调整和向下调整

为了跟我们以前的堆的比较形成对比，我在每个使用仿函数的地方都给出了之前的语句

		void adjust_up(int child)
		{
			Comapre comfunc;
			int parent = (child - 1) / 2;
			while (child > 0) {
				//if (_con[parent] < _con[child]){
				//if (comfunc.operator()(_con[parent], _con[child])){
				if (comfunc(_con[parent], _con[child])) {
					swap(_con[parent], _con[child]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else {
					break;
				}
			}
		}

		void adjust_down(int parent)
		{
			Compare comfunc;
			int child = parent * 2 + 1;
			while (child < _con.size()) {
				// 1.先选出左右孩子节点中较大的那个
				//if (child + 1 < _con.size() && _con[child] < _con[child + 1])
				if (child + 1 < _con.size() && comfunc(_con[child], _con[child + 1])) {
					child += 1;
				}
				// 2.将较大的那个节点跟父节点比较
				//if (_con[parent] < _con[child])
				if (comfunc(_con[parent], _con[child])) {
					swap(_con[child], _con[parent]);
					parent = child;
					child = parent * 2 + 1;
				}
				else {
					break;
				}
			}
		}

插入数据和删除数据

这也要考验你对堆的了解是否深入了！

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

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

其他常用接口

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

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

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

总概一览

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

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

	template<class T, class Container = vector<T>, class Compare = Myless<T>>
	class priority_queue
	{
	public:
		priority_queue() = default;

		template<class InputIterator>
		priority_queue(InputIterator first, InputIterator last)
		{
			// 1.把数据全部存放到存储数据的容器中
			while (first != last) {
				_con.push_back(*first);
				++first;
			}
			// 2.向下调整建堆，默认为大堆
			for (int i = (_con.size() - 2) / 2; i >= 0; i--) {
				adjust_down(i);
			}
		}

		void adjust_up(int child)
		{
			Comapre comfunc;
			int parent = (child - 1) / 2;
			while (child > 0) {
				//if (_con[parent] < _con[child]){
				//if (comfunc.operator()(_con[parent], _con[child])){
				if (comfunc(_con[parent], _con[child])) {
					swap(_con[parent], _con[child]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else {
					break;
				}
			}
		}

		void adjust_down(int parent)
		{
			Compare comfunc;
			int child = parent * 2 + 1;
			while (child < _con.size()) {
				// 1.先选出左右孩子节点中较大的那个
				//if (child + 1 < _con.size() && _con[child] < _con[child + 1])
				if (child + 1 < _con.size() && comfunc(_con[child], _con[child + 1])) {
					child += 1;
				}
				// 2.将较大的那个节点跟父节点比较
				//if (_con[parent] < _con[child])
				if (comfunc(_con[parent], _con[child])) {
					swap(_con[child], _con[parent]);
					parent = child;
					child = parent * 2 + 1;
				}
				else {
					break;
				}
			}
		}

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

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

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

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

		bool empty()
		{
			return _con.empty();
		}
	private:
		Container _con;
	};

}

使用效果如下：

总结

我写完这篇后，自认为还是蛮有成就感的，你呢？

秒客网