优先级队列priority_queue模拟实现-Toy模板网

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

🌟🌟hello，各位读者大大们你们好呀🌟🌟
🚀🚀系列专栏：【C++的学习】
📝📝本篇内容：C++容器优先级队列priority_queue模拟实现
⬆⬆⬆⬆上一篇：string模拟实现
💖💖作者简介：轩情吖，请多多指教(> •̀֊•́ ) ̖́-

1.优先级队列介绍

①优先级队列是一种容器适配器，它的第一个元素总是它所含的元素中最大的
②底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问
③优先级队列默认使用vector作为其底层存储数据的容器，在vector上又使用了堆算法，将vector中元素构造成堆的结构，因此priority_queue就是堆
注意：默认情况下priority_queue是大堆
④仿函数/函数对象（#include ）
默认情况下，创建的是大堆，其底层按照小于号比较
如果要创建小堆，将第三个模板参数换成greater比较方式
如果priority_queue中放自定义类型的数据，用户需要在自定义类型中提供>或<重载

2.模拟实现

#define _CRT_SECURE_NO_WARNINGS 1
#include <assert.h>
#include <vector>
#include <stdbool.h>
#include <iostream>
using namespace std;
namespace lnb
{
	//仿函数
	template<class T>
	struct less
	{
		//函数传参的（）重载
		bool operator()(const T& x,const T& y)const
		{
			return x < y;
		}
	};

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

	//默认大堆
	template<class T,class Container=vector<T>,class Compare=less<T>>
	class priority_queue
	{
	public:
		bool empty()
		{
			return _con.empty();
	    }
		size_t size()
		{
			return _con.size();
		}

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

		void Ajustup(int child)
		{
			int parent = (child - 1) / 2;
			//if (_con[parent] < _con[child])
				while (child>0)
				{
					if (Compare()(_con[parent], _con[child]))
					{
						swap(_con[parent], _con[child]);
						child = parent;
						parent = (child - 1) / 2;
					}
					else
					{
						break;
					}

				}

			



		}


		void push(const T& x)
		{
			_con.push_back(x);
			//向上调整
			Ajustup(_con.size() - 1);
		}

		void Adjustdown(int size, int parent)
		{
			int child = parent * 2 + 1;
			
			while (child < size)
			{
				if ((child+1<size)&&Compare()(_con[child], _con[child + 1]))//选择出左右孩子中大的那个
				{
					child++;
				}
				if (Compare()(_con[parent], _con[child]))
				{
					swap(_con[parent], _con[child]);
					parent = child;
					child = parent * 2 + 1;
				}
				else
				{
					break;
				}


			}





		}




		void pop()
		{
		swap(_con[0],_con[size() - 1]);
			_con.pop_back();
			Adjustdown(_con.size(),0);//向下调整
		
		}


	private:
		Container _con;
	};
}

🌸🌸优先级队列priority_queue模拟实现的知识大概就讲到这里啦，博主后续会继续更新更多C++的相关知识，干货满满，如果觉得博主写的还不错的话，希望各位小伙伴不要吝啬手中的三连哦！你们的支持是博主坚持创作的动力！💪💪文章来源地址https://www.toymoban.com/news/detail-433722.html

到了这里，关于优先级队列priority_queue模拟实现的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！