C++编程：实战教程 - 实现栈与队列（stack, queue）以及容器适配器 Queuedeque 缺陷解析 优先级队列（Priority Queue）基础练习与模拟构建 仿函数入门指南

 仿函数/函数对象——是个类，重载的是operator（），类对象可以像函数一样去使用，本质就是重载

（）也是一个运算符

跟sort不同，sort传的是函数模板，传的是对象，而这里传的是类模板 ，传的是类型

这里的lsFunc不是函数名 ，而是一个类对象

这俩个等价

 不仅有less，还有greater

namespace myspace
{
	template<class T>
	class less
	{
	public:
		bool operator()(const T& l, const T& r)const
		{
			return l < r;
		}
	};
	template<class T>
	class greater
	{
	public:
		bool operator()(const T& l, const T& r)const
		{
			return l > r;
		}
	};
}

 我们将这里全部改成小于号

 传入仿函数

 这样就可以去替换小于号

 小堆

大堆

完整代码

namespace myspace
{
	//大堆
	template<class T,class Container=vector<T>,class Compare=less<T>>
	class priority_queque
	{
	public:
		template<class InputerIterator>
		priority_queque(InputerIterator first, InputerIterator last)//迭代器区间
		{
			while (first < last)
			{
				_con.push_back(*first);
				++first;
			}
			//建堆
			for (int i = (_con.size() - 1 - 1)/2;i>=0;--i)
			{
				adjust_down(i);
		   }
		}
		priority_queque()//默认构造，不然会报错，因为上面的迭代器区间这个函数跟构造函数同名
		{}
		Compare com;
		void adjust_up(size_t child)
		{
			size_t parent = (child - 1) / 2;
			while (child>0)
			{
				if (com(_con[parent] , _con[child]))
				{
					std::swap(_con[parent], _con[child]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else
				{
					break;
				}
			}
		}
		void adjust_down(size_t parent)
		{
			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]))
				{
					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()
		{
			return _con.empty();
		}
		size_t size()const
		{
			return _con.size();
		}
	private:
		Container _con;
	};
}
namespace myspace
{
	template<class T>
	class less
	{
	public:
		bool operator()(const T& l, const T& r)const
		{
			return l < r;
		}
	};
	template<class T>
	class greater
	{
	public:
		bool operator()(const T& l, const T& r)const
		{
			return l > r;
		}
	};
}
int main()
{
	int a[]= { 156,132,156,156,31,5,15,31,364,15 };
	myspace::priority_queque<int,vector<int>,less<int>> pq(a,a+sizeof(a)/sizeof(int));
	while (!pq.empty())
	{
		cout << pq.top() << " ";
		pq.pop();
	}
	return 0;
}