priority_queue 模拟实现

priority_queue（优先队列）是一种特殊的队列数据结构，它的每个元素都有一个与之关联的优先级。在优先队列中，元素按照优先级的顺序进行排列，具有较高优先级的元素排在前面，较低优先级的元素排在后面。
C++标准库中的priority_queue：
priority_queue
下面是riority_queue的简单模拟实现：

#pragma once
#include <vector>
#include <iostream>
using namespace std;
namespace hsl
{
	template<class T, class Container = vector<T>,class Compar = Less<T>>
	class priority_queue
	{
	public:
		priority_queue()
		{}
		template <class InputIterator>
		priority_queue(InputIterator first, InputIterator last)
			:_con(first, last)
		{
			for (int i = (_con.size() - 2) / 2; i >= 0; i--)
			{
				adjust_down();
			}
		}


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


				if (child + 1 < _con.size() && com(_con[child] , _con[child + 1]))
				{
					++child;
				}


				if (com(_con[parent] , _con[child]))
				{
					swap(_con[parent], _con[child]);
					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];
		}


		bool empty()
		{
			return _con.empty();
		}
		size_t size()
		{
			return _con.size();
		}
	private:
		Container _con;
	};
	template<class T>
	class Less
	{
	public:
		const T& operator()(const T& a, const T& b)
		{
			return a < b;
		}
	};


	template<class T>
	class Greater
	{
	public:
		const T& operator()(const T& a, const T& b)
		{
			return a > b;
		}
	};
}	
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
117
118
119