【C++】priority_queue&&priority_queue模拟实现

zxctscl

发布于 2024-04-18 08:17:21

830

发布于 2024-04-18 08:17:21

文章被收录于专栏：zxctscl个人专栏

文章目录

1. priority_queue的介绍
2. priority_queue的使用
3. 函数模板与类模板
4. 仿函数
5. priority_queue模拟实现
- 5.1 push
- 5.2 pop
- 5.3 empty
- 5.4 size
- 5.5 top
- 5.6 仿函数实现大小堆
- 5.7 实现自定义类型的优先级队列
6. 附模拟实现代码

1. priority_queue的介绍

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

2. priority_queue的使用

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

来代码测试看看大堆：

void test_priority_queue()
{
	priority_queue<int> pq;
	pq.push(2);
	pq.push(1);
	pq.push(4);
	pq.push(3);

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

}
int main()
{
	test_priority_queue();
	return 0;
}

默认情况下，priority_queue是大堆

priority_queue默认情况下是less大堆，

想要priority_queue默认改为小堆，就得传三个参数。

用代码来测试一下:

#include<iostream>
using namespace std;
#include<vector>
#include<queue>

void test_priority_queue()
{
	priority_queue<int,vector<int>,greater<int>> pq;
	pq.push(2);
	pq.push(1);
	pq.push(4);
	pq.push(3);

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

}
int main()
{
	test_priority_queue();
	return 0;
}

3. 函数模板与类模板

sort默认排序也是升序

  vector<int> v = { 3,1,7,4,6,3 };
	// 升序
	sort(v.begin(), v.end());
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;

想要将sort排序默认改为降序，就得加仿函数：

    vector<int> v = { 3,1,7,4,6,3 };
	sort(v.begin(), v.end(), greater<int>());
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;

sort这里是函数模板，函数参数传的是对象。

而priority_queue传的是类型，需要显示实例化

4. 仿函数

仿函数就是一个函数对象，就是一个类型。先来实现一个类：

struct Less
{
	bool operator()(const int& x, const int& y)
	{
		return x < y;
	}
};
int main()
{
	Less lessfunc;
	cout << lessfunc(1, 2) << endl;
	cout << lessfunc.operator()(1, 2) << endl;
	cout << Less()(1, 2) << endl;
	return 0;
}

如果单独看红色框这一行，就会以为lessfunc是一个函数名，但它并不是，它是一个像函数的对象。

仿函数它的对象可以像函数一样去使用，本质上就是调用operator(): 这两个是等价的：

还有能用匿名对象：

它本质上就是：

这里重载函数调用参数的()，其实就像[]一样，v[0]也就是v.operator：

本质上就是参数留下，变成运算符的操作数。运算符重载中operator加运算符才是函数名，省略掉的就是.operator加括号。一个类只要重载了operator()就可以调仿函数。

加模板就直接可以重载为泛型，什么类型就可以支持。

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;
}

这里定义类用struct和class有什么区别？一般所有数据都公有就用struct，有些公有，有些私有就用class。

5. priority_queue模拟实现

直接复用容器

5.1 push

插入一个数据后，向上调整，具体实现过程有需要可以看【数据结构】堆的实现

push代码：

		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;
				}
			}
		}
		void push(const T& x)
		{
			_con.push_back(x);
			adjust_up(_con.size() - 1);
		}

5.2 pop

就这样删除效率太低了，通常首位交换一下。向下调整，具体实现过程有需要可以看【数据结构】堆的实现

pop代码实现：

		void adjust_down(size_t parent)
		{
			size_t child = parent * 2 + 1;
			while (child< _con.size())
			{
				if (child + 1<_con.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;
				}
			}

		}

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

5.3 empty

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

5.4 size

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

5.5 top

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

5.6 仿函数实现大小堆

想要大堆改小堆可以直接在代码上面修改，但是要实现大堆，代码又得重新修改。这里就得用到上面提到的仿函数了。写两个仿函数，一个实现大堆，一个实现小堆。

大堆实现：

	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;
		}
	};

在写类模板的时候就把仿函数也一起传过去

template<class T, class Container = vector<T>, class Compare = less<T>>

5.7 实现自定义类型的优先级队列

定义一个日期类：

class Date
{
public:
	friend ostream& operator<<(ostream& _cout, const Date& d);

	Date(int year = 1900, 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);
	}
private:
	int _year;
	int _month;
	int _day;
};
ostream& operator<<(ostream& _cout, const Date& d)
{
	_cout << d._year << "-" << d._month << "-" << d._day;
	return _cout;
}

用priority_queue来实现日期排序：

但是如果给的是指针：

传地址每次给的结果不一样。 new不能保证每次new的地址都比前面的大，这里就得重新写一个仿函数。

class GreaterPDate
{
public:
	bool operator()(const Date* p1, const Date* p2)
	{
		return *p1 > *p2;
	}
};

这个时候传地址就不会在变了：

所以说仿函数控制比较逻辑，可以控制用什么去比较。

6. 附模拟实现代码

#pragma once
#include<vector>

namespace bit
{
	template<class T>
	class less
	{
	public:
		bool operator()(const T& x, const T& y)
		{
			return x < y;
		}
	};

	template<class T>
	class greater
	{
	public:
		bool operator()(const T& x, const T& y)
		{
			return x > y;
		}
	};

	
	template<class T, class Container = vector<T>, class Compare = less<T>>
	class priority_queue
	{
	public:
		void adjust_up(size_t child)
		{
			Compare com;
			size_t parent = (child - 1) / 2;
			while (child > 0)
			{
				//if (_con[child] > _con[parent])
				//if (_con[parent] < _con[child])
				if (com(_con[parent], _con[child]))
				{
					std::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(size_t parent)
		{
			Compare com;
			size_t child = parent * 2 + 1;
			while (child < _con.size())
			{
				//if (child + 1 < _con.size() && _con[child + 1] > _con[child])
				//if (child + 1 < _con.size() && _con[child] < _con[child + 1])
				if (child + 1 < _con.size() && com(_con[child], _con[child + 1]))
				{
					++child;
				}

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

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

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

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

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

	private:
		Container _con;
	};


}

有问题请指出，大家一起进步！！！

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-04-17，如有侵权请联系 cloudcommunity@tencent.com 删除

容器