STL-priority-queue优先级队列

priority_queue 优先级队列

堆的概念

STL中的 priority_queue 是数据结构中的堆，堆的本质是一个完全二叉树，而堆又分为大根堆和小根堆。

• 小根堆（min heap）：任意节点的值 ≤ 其子节点的值。
• 大根堆（max heap）：任意节点的值 ≥ 其子节点的值。
  

我们将二叉树的根节点称为“堆顶”，将底层最靠右的节点称为“堆底”。不难发现，对于大顶堆（小顶堆），堆顶元素（根节点）的值总是最大（最小）的。

堆的存储结构

堆是一个非线性的树形结构，但是在计算机实现当中，我们往往是采用数组的形式进行存储。

在这一段数组中，我们使用公式来判断一个节点的子节点和父节点。

堆节点公式
给定索引 i ，其左子节点的索引为 2 i + 1 ，右子节点的索引为 2 i + 2 ，父节点的索引为 ( i − 1 ) / 2 （向下整除）。当索引越界时，表示空节点或节点不存在。

如何建堆

给定一个数组，我们要如何才能实现堆的逻辑结构呢？这涉及到建堆操作，堆分为大根堆和小根堆的，堆总是有序的。其实建堆就是把数组中的数据按照堆的逻辑结构（完全二叉树）进行大小排序，就可以完成建堆操作。

那么我们怎样才能实现按照堆的逻辑结构进行排序呢？首先堆是分为大小根堆的，STL 中默认为大根堆，那么我们首先实现大根堆排序建堆。

大根堆是根节点最大，叶子节点最小的排序方式。按照常规排序思想，我们首先从最后一个叶子节点开始排序。

向上调整建堆

在这里我们会遇到一个问题，该怎样进行排序？大根堆最基本的逻辑就是父亲节点的值总是大于子节点的值，所以我们首先比较左右子节点值的大小，比较得出是左子树的值大还是右子树的值大，然后再使用较大的子节点值与父亲节点值进行比较，如果子节点值小于父亲节点值，则不进行任何操作这已经满足堆的逻辑，反之进行值替换，接着将子节点重新赋值为父亲节点，再重新计算父亲节点进入下一轮值比较，直至达到根节点或者子节点值小于父亲节点值时，停止排序。

这是向上调整建堆的思路，但是这个思路有一个致命问题：向上调整是从叶子节点开始，每次只调整一个元素，导致最坏情况下，向上排序建堆的时间复杂度为 O(nlogn) 。

向下调整建堆

向下调整的核心思想是从下到上依次调整一个子树。

向下调整思想将数据分为多个子树，每个子树只需向下调整好自己的子树，保证自己一定是一个大根堆，从后往前依次调整（子树 1 -> 子树 2 -> 子树 3），自然地最终我们的堆就排好序了。最终向下调整算法的时间复杂度为 O(n) 。

template<class T, class Container = vector<T>>
class priority_queue
{
private:
	// 向上调整算法
	void AdjustUp(int child)
	{
		int parent = (child - 1) / 2;

		while(child > 0 && _con[child] > _con[parent])
		{
			std::swap(_con[child], _con[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
	}

	// 向下调整算法
	void AdjustDown(int parent)
	{
		int child = parent * 2 + 1;

		while (child < _con.size())
		{
			int max_value = child + 1 < _con.size() && _con[child] < _con[child + 1] ? child + 1 : child;
			if (_con[parent] < _con[max_value])
			{
				std::swap(_con[parent], _con[max_value]);
				parent = max_value;
				child = parent * 2 + 1;
			}
			else
			{
				break;
			}
		}
	}
public:
	// 建堆
	template<class InputIterator>
	priority_queue(InputIterator first, InputIterator last)
	{
		// 将迭代器区间中的元素插入到容器中
		while (first != last)
		{
			_con.push_back(*first);
			++first;
		}

		// 从最后一个非叶子节点开始调整
		for (int i = (_con.size() - 1 -1) / 2; i >= 0; --i)
		{
			// 向下调整算法
			AdjustDown(i);
		}
	}
private:
	Container _con;
}

STL priority_queue 实现

STL 中堆的实现并不复杂，它和 queue、stack 一样采用了容器适配器的设计，默认容器设置为 vector 。因为 vector 非常适合作为 priority_queue 的底层容器，至于为什么前面已经讨论过原因了。

// priority_queue 默认大根堆
template<class T, class Container = vector<T>>
class priority_queue
{
private:
	// 向下调整
	void AdjustDown(int parent)
	{
		int child = parent * 2 + 1;

		while (child < _con.size())
		{
			int max_value = child + 1 < _con.size() && _con[child] < _con[child + 1] ? child + 1 : child;
			if (_con[parent] < _con[max_value])
			{
				std::swap(_con[parent], _con[max_value]);
				parent = max_value;
				child = parent * 2 + 1;
			}
			else
			{
				break;
			}
		}
	}

	// 向上调整
	void AdjustUp(int child)
	{
		int parent = (child - 1) / 2;

		while(child > 0 && _con[child] > _con[parent])
		{
			std::swap(_con[child], _con[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
	}

public:
	typedef typename Container::iterator iterator;
	typedef typename Container::const_iterator const_iterator;

	iterator begin()
	{

		return _con.begin();
	}

	iterator end()
	{
		return _con.end();
	}

	priority_queue()
	{
	}

	~priority_queue()
	{
		clear();
	}

	template<class InputIterator>
	priority_queue(InputIterator first, InputIterator last)
	{
		// 将迭代器区间中的元素插入到容器中
		while (first != last)
		{
			_con.push_back(*first);
			++first;
		}

		// 从最后一个非叶子节点开始调整
		for (int i = (_con.size() - 1 -1) / 2; i >= 0; --i)
		{
			AdjustDown(i);
		}
	}

	void pop()
	{
		std::swap(_con[0], _con[_con.size() - 1]);
		_con.pop_back();
		AdjustDown(0);
	}

	void push(const T& value)
	{
		_con.push_back(value);
		AdjustUp(_con.size() - 1);
	}

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

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

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

	void clear()
	{
		_con.clear();
	}

	void swap(priority_queue& other)
	{
		std::swap(_con, other._con);
	}
private:
	Container _con;
};