C++ ：优先级队列

仿函数：

在写优先级队列前，先简单说明一下仿函数，仿函数是一个能够实现函数功能的类，但类中必须重载operator()运算符，因为调用仿函数就是通过类对象调用重载后的operator()运算符的，例如：

class Func { public: 	void operator()()//可以控制返回值和参数 	{ 		cout << "void operator()()" << endl; 	} }; int main() { 	Func f; 	f(); 	return 0; }

 这个运算符重载不像其他的运算符重载一样，operator()的返回值和参数可以进行较大改动

建立大堆用的仿函数：

优先级队列其实类似于堆，有过之前对堆的实现其实就很好理解优先级队列了

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

建立小堆用的仿函数：

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

 仿函数在这里体现的优点是当我们建立大堆或小堆时，不用像之前一样再去AdjustDown()和AdjustUp()中改变>或<符号，而是可以通过仿函数来直接进行实现：

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

priority_queue<int,vector<int>,mygreater<int>> p1;//小堆 priority_queue<int, vector<int>, myless<int>> p1;//大堆

push:

		void Adjust_Up(int child) 		{ 			int parent = (child - 1) / 2; 			while (child > 0) 			{ 				Compare com; 				if (com(_con[parent] , _con[child])) 				{ 					swap(_con[parent], _con[child]); 					child = parent; 					parent = (child - 1) / 2; 				} 				else 				{ 					break; 				} 			} 		} 		void push(const T& val) 		{ 			_con.push_back(val); 			Adjust_Up(_con.size()-1); 		}

 pop:

		void AdjustDown(int parent, int n) 		{ 			int child = parent * 2 + 1; 			Compare com; 			while (child < n) 			{ 				if (child + 1 < n && com(_con[child] , _con[child+1])) 				{ 					child++; 				} 				if (com(_con[parent] , _con[child])) 				{ 					swap(_con[child], _con[parent]); 				} 				else 				{ 					break; 				} 			} 		} 		void pop() 		{ 			swap(_con[0], _con[_con.size() - 1]); 			_con.pop_back(); 			AdjustDown(0,_con.size()); 		}

 empty:

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

top:

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

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

 构造建堆：

		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--) 			{ 				AdjustDown(i, _con.size()); 			} 		}