• priority_queue简单实现（优先级队列）（c++）

    priority_queue

    priority_queue介绍

    pri_que是一个容器适配器，它的底层是其他容器，并由这些容器再封装而来。类似于heap的结构。默认为大堆。
    在这里插入图片描述

    逻辑实现

    框架

    namespace xty 
{
	template<class T, class Container = vector<T>, class Compare = less<T>>
	class priority_queue
	{

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

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

		const T& top()
		{
			return _con.front();
		}


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

	private:
		Container _con;
	};
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39

    调整算法

    因为优先级队列是以堆为结构实现的，因此插入删除要保持堆的结构，需要adjust_up()和adjust_down()两个算法。
    建堆算法详细参考

    adjust_up()

    向上调整，由堆底一直调整到堆顶。

    		void adjust_up(int child)
		{
			int parent = (child - 1) / 2;

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18

    adjust_down()

    向下调整，由堆顶一直向下调整直到叶子。

    		void adjust_down(int parent)
		{
			size_t child = 2 * parent + 1;
			while (child < _con.size())
			{
				if (child + 1 < _con.size() && _con[child + 1] > _con[child])
				{
					child++;
				}
				if (_con[child] > _con[parent])
				{
					swap(_con[child], _con[parent]);
					parent = child;
					child = 2 * parent + 1;
				}
				else
				{
					break;
				}
			}
		}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21

    仿函数/比较函数

    我们观察到库的模板参数给了三个，其中第一个参数是数据类型，第二个参数是模板容器，第三个参数就是仿函数（用户可以自己制定比较规则！），默认为大堆less。

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

    • 1

    接下来我们实现一个比较类：

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

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17

    然后我们微调调整函数的逻辑将if的内容改成比较函数：
    因为使用方法酷似函数，因此它叫仿函数 ！

    		void adjust_up(int child)
		{
			Compare com;  //实例化比较函数
			int parent = (child - 1) / 2;

			while (child > 0)
			{
				if (com(_con[child], _con[parent]))
				/*if (_con[child] > _con[parent])*/
				{
					swap(_con[child], _con[parent]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else
				{
					break;
				}
			}
		}

		void adjust_down(int parent)
		{
			Compare com;  //实例化比较函数
			size_t child = 2 * parent + 1;
			while (child < _con.size())
			{
				if (child + 1 < _con.size() && com(_con[child + 1], _con[child]))
				{
					child++;
				}
				if (com(_con[child], _con[parent]))
				{
					swap(_con[child], _con[parent]);
					parent = child;
					child = 2 * parent + 1;
				}
				else
				{
					break;
				}
			}
		}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43

    仿函数特性

    有了仿函数的功能后，我们可以自己定义比较类型，使程序设计更加灵活。

    看下面一段代码：

    	class Date
	{
	public:
		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);
		}

		friend ostream& operator<<(ostream& _cout, const Date& d)
		{
			_cout << d._year << "-" << d._month << "-" << d._day;
			return _cout;
		}

	private:
		int _year;
		int _month;
		int _day;
	};


	void test_priority_queue2()
	{
		// 大堆，需要用户在自定义类型中提供<<的重载
		//priority_queue q1;
		priority_queue<Date, vector<Date>, greater<Date>> q1;
		q1.push(Date(2018, 10, 29));
		q1.push(Date(2018, 10, 30));
		q1.push(Date(2018, 10, 28));
		cout << q1.top() << endl;
	}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46

    首先这段测试代码结果是唯一的：
    在这里插入图片描述
    而如果我们增加另一种格式的代码呢？

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

	class PDateGreater
	{
	public:
		bool operator()(const Date* p1, const Date* p2)
		{
			return *p1 > *p2;
		}
	};
	void test_priority_queue2()
	{
		//priority_queue, PDateLess> q2;
		priority_queue<Date*, vector<Date*>, PDateGreater> q2;
		q2.push(new Date(2018, 10, 29));
		q2.push(new Date(2018, 10, 30));
		q2.push(new Date(2018, 10, 28));
		cout << *(q2.top()) << endl;
	}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26

    这段代码如果不写仿函数，结果是不唯一的，因为比较的是指针，重写仿函数后，答案就唯一了！！可以看见，仿函数可以使我们比较数据更加灵活！

    构造函数

    显然我们没有写构造函数，程序并没有报错，是因为：

    • 我们不写构造函数，编译器会默认生成一个。而成员函数是自定义类型，会调用自定义类型的构造函数，所以程序没有问题运行。
    • 当我们写了构造函数之后，编译器就不会再默认生成了，需要我们自己写。

    迭代器区间构造

    因为自己显示写了构造函数，编译器不再默认生成默认构造函数，需要自己再显示补一个默认构造！

    		//默认构造
		priority_queue(){}
		
		template<class InputIterator>
		priority_queue(InputIterator first, InputIterator last)
		{
			Container _con;
			while (first!= last)
			{
				push(*first);
				first++;
			}
		}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13

    完整优先级队列代码

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

	template<class T>
	struct grater
	{
		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(int child)
		{
			Compare com;  //实例化比较函数
			int parent = (child - 1) / 2;

			while (child > 0)
			{
				if (com(_con[child], _con[parent]))
				/*if (_con[child] > _con[parent])*/
				{
					swap(_con[child], _con[parent]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else
				{
					break;
				}
			}
		}

		void adjust_down(int parent)
		{
			Compare com;  //实例化比较函数
			size_t child = 2 * parent + 1;
			while (child < _con.size())
			{
				if (child + 1 < _con.size() && com(_con[child + 1], _con[child]))
				{
					child++;
				}
				if (com(_con[child], _con[parent]))
				{
					swap(_con[child], _con[parent]);
					parent = child;
					child = 2 * parent + 1;
				}
				else
				{
					break;
				}
			}
		}


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

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

		const T& top()
		{
			return _con.front();
		}


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

		priority_queue(){}
		
		template<class InputIterator>
		priority_queue(InputIterator first, InputIterator last)
		{
			Container _con;
			while (first!= last)
			{
				push(*first);
				first++;
			}
		}


	private:
		Container _con;
	};
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
  • 相关阅读:
    利用无线技术实现分散传感器信号远程集中控制
    测试 SAP 电商云 Spartacus UI 3.4.x 和 4.3.x 的 guest checkout 功能
    零基础HTML教程(31)--HTML5多媒体
    两日总结十六
    linux下敏感文件（账号密码）查找—内网渗透linux主机密码收集
    java计算机毕业设计敬老院管理系统源码+数据库+系统+lw文档+mybatis+运行部署
    linux的常见命令
    VR危险环境模拟介绍|VR虚拟现实设备
    理解思想：Python多线程和并发编程
    你知道有什么好的文字翻译软件吗？这几个软件非常好用
  • 原文地址：https://blog.csdn.net/weixin_45153969/article/details/134545774