【C++ STL】priority_queue模拟

前言

• priority_queue文档

priority_queue是一种拥有权值概念的queue。其允许按照不同的顺序将元素依次新增到其中，然后按照元素的权值（一种比较方法）进行排列。

• priority_queue本质就是一个heap。缺省情况下，就是一个以vector为底层容器的完全二叉树。
• 小编写了一文专门谈heap算法

本文章，小编主要带大家模拟实现一个priority_queue。主要目的：

1. 体会模板编程
2. 体会仿函数的运用

模拟实现priority_queue

• 我们先来看STL中的priority_queue：

  
  这里有三个模板参数：

  1. T：存储的数据类型。
  2. Container：底层使用的容器类型。缺省是vector<T>。几乎是最佳的选择了。满足所有priority_queue的实现所有需求。
  3. Compare：比较方法。因为逻辑结构的完全二叉树，根和左右孩子的确定是需要有键值/权值进行比较方法的。例如：int的比较方法就是数值的比较方法。即less<T>的实现或许是这样的：template<class T> struct less {bool operator(const T& x, const T& t){return x < y}};根据我们类型的不同和想要比较的方法不同，我们可以自定义传入自己想要的比较方法。

我们就先将自己实现的框架搭建一下

namespace LL
{
	template <class T>
	struct less //less默认建大堆；可以理解为sort_heap之后是升序
	{
		bool operator()(const T& x, const T& y)
		{
			return x < y;
		}
	};

	template<class T, class Container = std::vector<T>, class Compare = LL::less<T>>
	class priority_queue
	{
	public:
		priority_queue()
		{ }

	private:
		Container _con; //容器
		Compare _com; //比较方法
	};

}

1. 两种调整算法

• 由于priority_queue需要维护大根堆/小根堆的性质。所以每次插入删除数据之后都需要对原有的数据进行调整，以满足大根堆/小根堆的性质。
• 注意：这里的实现和另一文的接口实现不同。因为在哪里需要考虑sort。这里不需要考虑，所以不需要求有效长度。

1.1 向上调整

void adjustup(int index)
{
	int parent = (index - 1) / 2;
	while (index > 0)
	{
		if (_com(_con[parent], _con[index])) //如果parent < index发生交换
		{
			std::swap(_con[parent], _con[index]);
			index = parent;
			parent = (index - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

1.2 向下调整

void adjustdown(int index)
{
	int child = 2 * index + 1, size = (int)_con.size(); //左孩子位置
	//因为这里不存在sort_heap算法，所以我们调整一下接口
	while (child < size)
	{
		if (child + 1 < size && _com(_con[child], _con[child + 1]))
		{
			child = child + 1; //更新为右孩子
		}
		if (_com(_con[index], _con[child]))
		{
			std::swap(_con[index], _con[child]);
			index = child;
			child = 2 * index + 1;
		}
		else
		{
			break;
		}
	}
}

2. push和pop

完成push和pop的操作也很简单。就是实现一个push_heap算法和pop_heap算法。

void push(const T& val)
{
	_con.push_back(val);
	int index = (int)_con.size() - 1;
	adjustup(index);
}

void pop()
{
	int last = (int)_con.size() - 1;
	std::swap(_con[0], _con[last]); //交换
	_con.pop_back();
	adjustdown(0); //因为pop之后，需要调整的位置是0
}

3. empty和top

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

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

4. 迭代器构造建堆

• 传入一个迭代器，我们利用迭代器的元素进行make_heap操作。

template <class RandomAccessIterator>
priority_queue(RandomAccessIterator first, RandomAccessIterator last)
{
	while (first != last) //将元素加入到容器中
	{
		_con.push_back(*first);
		++first;
	}
	int index = (int)_con.size() - 1; //最后一个元素的下标
	//从后遍历每个父亲节点，使每个元素的父亲节点的局部满足heap结构
	for (int i = (index - 1) / 2; i >= 0; --i)
	{
		adjustdown(i); //从父亲节点开始向下调整
	}
}

完。