[STL]优先级队列的模拟实现（堆）

        优先级队列的基本操作实现时：需要两个重要的调整:向上调整算法(Adjust_up)，向下调整算法(Adjust_down)。初次之外，还有一个拟函数的重要思想和实现操作来帮助我们实现大堆和小堆的转换。

基础框架：（这里我们同样采用适配器的写法）

template<class T, class Container=vector<T>,class Compare = less<T> >
	class priority_queue
	{
        public:
        void Adjust_up();
        void Adjust_down();
        void push(const T &x);
        void pop();
        const T& top();
        int size();
        bool empty();
        private:
        Container _con;
    }
​

​

那么我们先来看这两种算法（前面的堆相关文章有详细解说，即此处只呈现代码）： 

1.向上调整算法：

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

2.向下调整算法：

void Adjust_down(int parent)
		{
			int child = parent * 2 + 1;
			while (child < _con.size())
			{

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

拟函数：

作用: 简单来说，就是可以把 类的对象 用函数的方式使用，也就是模拟函数的使用。

其实质上是利用类对( )操作符的重载:

         ls(a,b)模拟函数名加传参的操作，但实际上是一个对象调用了运算符函数。所以我们再利用模板就可以实现对优先级队列中优先级进行随时的更改（就是这个优先级队列是大堆还是小堆）。

        所以，我们又有知道模板可以传一个容器，或者自定义的类型：

因此，最终呈现的优先级队列模拟的代码也要因此修改：（主要是修改两个重要调整算法里面的比较）：

template<class T>
	struct less
	{
		bool operator()(const T& x, const T& y)
		{
			return x < y;
		}
	};
	template<class T>
	struct greater
	{
		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 (_con[child] > _con[parent])
				if (com(_con[parent],_con[child]))
				{
					swap(_con[child], _con[parent]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else
				{
					break;
				}
				
			}
		}	
		void Adjust_down(int parent)
		{
			Compare com;
			int 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[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()
		{
			swap(_con[0], _con[_con.size() - 1]);
			_con.pop_back();
			Adjust_down(0);
		}

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

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


	private:
		Container _con;
	};

        以上就是优先级队列实现的重点，掌握之后就能轻松实现了，小伙伴们学会了吗？如有不妥的地方，请小伙伴们指正哦~，下次再见。