priority_queue模拟实现

目录

前言

伪函数

具体实现

成员变量

向上调整 Adjust_UP

向下调整 Adjust_Down

构造函数

push

pop

top

size

empty

析构

总结

前言

priority_queue是一个适配器(适配器没有迭代器)。 其底层是堆。 可适配容器默认为vector。 通过priority_queue的模拟实现的来理解 仿函数 和 可适配容器

伪函数

通过对一个类的 运算符() 进行重写，来达到后面通过该类的实例化对象来达到函数的效果。 具体可看下文 伪函数 在 priority_queue中的运用

    template<class T>
	struct less
	{
		bool operator()(const T& left, const T& right)
		{
			return left < right;
		}
	};

具体实现

成员变量

Container是可适配容器， Compare 是伪函数

//priority的template
template<class T , class Container = vector<T> , class Compare = less<T>>

//成员变量
	private:
		Container _v;
		Compare compare;

向上调整 Adjust_UP

这里提问一下读者，该文是建的小堆。 那么如何建造大堆呢？ (答案在末尾）

void Adjust_UP(size_t pos)
{
	int child = pos;
	int parent = (child - 1) / 2;
	while (child)
	{
		if (compare(_v[child], _v[parent]))
		{
			std::swap(_v[child], _v[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

向下调整 Adjust_Down

这里提问一下读者，该文是建的小堆。 那么如何建造大堆呢？ (答案在末尾）

void Adjust_Down(size_t pos)
{
	int parent = pos;
	int child = parent * 2 + 1;
	while (child < _v.size())
	{
		if (child + 1 < _v.size() && compare(_v[child + 1] , _v[child])) child++;

		if (compare(_v[child] , _v[parent]))
		{
			std::swap(_v[child], _v[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

构造函数

priority_queue()
{
	_v();
}

template<class InputIterator>
priority_queue(InputIterator b, InputIterator e)
{
	while (b != e)
	{
		_v.push_back(*b);
		++b;
	}
	//向上调整建堆
	int parent = (_v.size() - 1 - 1) / 2;
	for (; parent > 0; parent--)
	{
		Adjust_Down(parent);
	}
}

template<class T>
priority_queue(initializer_list<T> v)
{
	//for (const auto& x : v) push(x);

	for (const auto& x : v) _v.push_back(x);
	//向上调整建堆
	int parent = (_v.size() - 1 - 1) / 2;
	for (; parent > 0; parent--)
	{
		Adjust_Down(parent);
	}
	
}

push

void push(const T& x)
{
	_v.push_back(x);
	Adjust_UP(_v.size() - 1);
}

pop

void pop()
{
	swap(_v[0], _v[_v.size() - 1]);
	_v.pop_back();
	Adjust_Down(0);
}

top

T& top()
{
	return _v.front();
}

size

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

empty

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

析构

析构的话没必要写，结尾的时候 默认生成的析构函数 会调用 可适配容器 的 析构函数(即文中的vector 的析构函数)

总结

通过priority_queue的模拟实现来更好的理解伪函数。

问题答案： 将Adjust_Down 和 Adjust_UP 中的 compare中的参数对调即可。