priority_queue实现错误总结

错误代码展示

#pragma once

#include<vector>
#include<iostream>
using namespace std;

namespace bit
{
	template<class T,class Container=vector<T>,class Com = less<T>>
	class priority_queue
	{
	public:
		priority_queue() = default;
		template<class Iterator>
		priority_queue(const Iterator& first, const Iterator& end)
			:_con(first,end)
		{
			for (int i = _con.size() - 1; i >= 0; i--)
				_down(i);
		}
		T top()
		{
			return _con[0];
		}
		int size()
		{
			return _con.size();
		}
		void push(const T& val)
		{
			_con.push_back(val);
			_up(_con.size()-1);
		}
		void pop()
		{
			swap(_con[0], _con[_con.size()-1]);
			_con.pop_back();
			_down(0);
		}
	private:
		void _up(int child)
		{
			Com com;
			int parent = (child - 1) / 2;
			while (child > 0)
			{
				if (com( _con[child],_con[parent])) swap(_con[child], _con[parent]);
				child = parent;
				parent = (child - 1) / 2;
			}
		}
		void _down(int parent)
		{
			Com com;
			int n = _con.size();
			int child = parent * 2 + 1;
			//while (child < n && child + 1 < n)
			// 两个child能不能交换都要先进去
			while (child < n)
			{
				if (child + 1 < n
					&& com( _con[child + 1],_con[child]))
					child++;
				if (com(_con[child],_con[parent] )) swap(_con[parent], _con[child]);
				parent = child;
				child = parent * 2 + 1;
			}
		}
		Container _con;
	};
	template<class T>
	struct less
	{
		bool operator()(T& a, T& b)
		{
			return a > b;
		}
	};

	void test()
	{
		priority_queue<int,vector<int>,less<int>> q;
		q.push(1);
		q.push(2);
		q.push(5);
		q.push(3);
		while (q.size())
		{
			cout << q.top() << " ";
			q.pop();
		}

		puts("");
		vector<int> v({ 2,3,6,4,1 });
		// 大根堆
		priority_queue<int, vector<int>, less<int>> q1(v.begin(), v.end());
		while (q1.size())
		{
			std::cout << q1.top() << " ";
			q1.pop();
		}
		puts("");
		priority_queue<int> q2(v.begin(), v.end());
		while (q2.size())
		{
			std::cout << q2.top() << " ";
			q2.pop();
		}
	}
}

这个代码应该达到的效果是，三组结果都是大根堆，但是看到的确实第三组是小根堆

正确代码

#pragma once

#include<vector>
#include<iostream>
// using namespace std;
// 不能将std命名空间放开，如果放开，自己写的less和空间中的less重名，在没有传比较参数的情况下就会调用库中的less
// 

namespace bit
{
	// 原本自我实现的less对应的是库中的greater，为了让自己的priority_queue能呈现大根堆的形式，将priority_queue的比较顺序进行了对调，导致在默认参数调用库中的less的时候会出现反向的情况
	// 在实现正确的情况下，less的位置是可以随便放置的
	// 在同一个文件中，库函数在上下找using namespace std;
	// 在引用自己的文件中，库函数在上面找using namespace std;
	
	//template<class T>
	//struct less
	//{
	//	bool operator()(T& a, T& b)
	//	{
	//		return a > b;
	//	}
	//};
	template<class T>
	struct less
	{
		bool operator()(T& a, T& b)
		{
			return a < b;
		}
	};
	template<class T,class Container=std::vector<T>,class Com = less<T>> //
	class priority_queue
	{
	public:
		priority_queue() = default;
		template<class Iterator>
		priority_queue(const Iterator& first, const Iterator& end)
			:_con(first,end)
		{
			for (int i = _con.size() - 1; i >= 0; i--)
				_down(i);
		}
		T top()
		{
			return _con[0];
		}
		int size()
		{
			return _con.size();
		}
		void push(const T& val)
		{
			_con.push_back(val);
			_up(_con.size()-1);
		}
		void pop()
		{
			std::swap(_con[0], _con[_con.size()-1]);
			_con.pop_back();
			_down(0);
		}
	private:
		void _up(int child)
		{
			Com com;
			int parent = (child - 1) / 2;
			while (child > 0)
			{
				if (com( _con[parent],_con[child])) std::swap(_con[child], _con[parent]);
				child = parent;
				parent = (child - 1) / 2;
			}
		}
		void _down(int parent)
		{
			Com com;
			int n = _con.size();
			int child = parent * 2 + 1;
			//while (child < n && child + 1 < n)
			// 两个child能不能交换都要先进去
			while(child < n)
			{
				if (child +1 < n 
					&& com(_con[child],_con[child + 1])) 
					child++;
				if (com( _con[parent], _con[child])) std::swap(_con[parent], _con[child]);
				parent = child;
				child = parent * 2 + 1;
			}
		}
		Container _con;
	};

	void test()
	{
		priority_queue<int,std::vector<int>,less<int>> q;
		q.push(1);
		q.push(2);
		q.push(5);
		q.push(3);
		while (q.size())
		{
			std::cout << q.top() << " ";
			q.pop();
		}

		puts("");
		std::vector<int> v({ 2,3,6,4,1 });
		// 大根堆
		priority_queue<int, std::vector<int>, less<int>> q1(v.begin(), v.end());
		while (q1.size())
		{
			std::cout << q1.top() << " ";
			q1.pop();
		}
		puts("");
		priority_queue<int> q2(v.begin(), v.end());
		while (q2.size())
		{
			std::cout << q2.top() << " ";
			q2.pop();
		}
	}
}