优先级队列的使用及模拟实现

Test.cpp

#include 
#include 
#include 
using namespace std;

#include "Priority_queue.h"

void test_priority_queue()
{
	//默认是大的数优先级高，证明底层是大堆
	jpc::priority_queue<int> pq; //无参 去初始化
	pq.push(3);
	pq.push(1);
	pq.push(2);
	pq.push(5);
	pq.push(0);
	pq.push(1);

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


	int a[] = {3,2,7,6,0,4,1,9,8,5};
	//priority_queue heap(a,a+sizeof(a)/sizeof(int)); //用一段区间去初始化 //大的数优先级高（大堆）
	jpc::priority_queue<int,vector<int>,greater<int>> heap(a, a + sizeof(a) / sizeof(int)); //小的数字优先级高（小堆）

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

}

int main()
{
	test_priority_queue();

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

Priority_queue.h

#pragma once

namespace jpc
{
	//大堆
	template<class T,class Container = vector<T>,class Compare=std::less<T>> 
	// Compare是进行比较的仿函数  less->大堆
	// Compare是进行比较的仿函数  greater->小堆
	class priority_queue
	{
	public:
		//通过 迭代器区间 构造函数
		template<class InputIterator>
		priority_queue(InputIterator first, InputIterator last)
		{
			while (first != last)
			{
				_con.push_back(*first);
				++first;
			}

			//建堆(从最后一个非叶子结点开始 向下 调整)
			for (int i = (_con.size() - 1 - 1) / 2; i >= 0; --i)
			{
			    adjust_down(i);
			}
		}


		//无参的构造函数（通过初始化列表调用默认构造函数）
		priority_queue()
		{}

		
		// 其时间复杂度为：logN
		void adjust_up(size_t child)  // 从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;
				}
			}
		}

		// logN
		void adjust_down(size_t parent)  // 从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 push(const T& x)
		{
			_con.push_back(x);
			adjust_up(_con.size()-1); //向上调整
		}

        //删除（尾删）
		void pop()
		{
			std::swap(_con[0],_con[_con.size()-1]);
			_con.pop_back();

			adjust_down(0);
		}

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

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

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

		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
117
118
119
120
121
122
123
124
125
126