C++优先级队列模拟实现

实现思路：

（1）优先级队列底层默认使用vector模拟堆实现，因此要对vector中的元素进行修改，使其具有堆的性质。

（2）建堆——堆的要求是任何一个结点都比其孩子结点小或者大。如果一个结点只是比其孩子结点小或者大，而它的孩子结点不满足堆的性质，则该结构不具有堆性质，因此我们可以先从底层开始往上层走，这样先让底层具有堆的性质，则再实现上层堆性质时就不必再考虑下层。由于叶子结点本身就具有堆的性质，因此从最后一个非叶子结点开始实现堆结构，如果是实现大堆，则比较父亲结点和孩子结点中较大的那个，如果小于，则交换，一个结点向下调整完毕后，调整下一个非叶子结点，直到调整到根节点结束。

（3）堆的插入——插入新的元素以后，由于原堆是具有堆性质的，因此将新插入的元素进行向上调整，如果是大堆，则它如果比其父节点大，则交换，直到达到根节点，或者比其父节点小。

（4）堆的删除——堆只能删除根节点，主要是为了像栈和队列那样具有意义，堆的删除即出最大或者最小的那个元素。可以将堆顶元素与堆尾元素进行交换，然后将堆的大小缩小一个元素大小，再对堆顶元素进行向下调整。

（5）通过传入模板类型来表示自己想创建大堆还是小堆，以及底层结构用什么。因为模板参数是一种类型，因此可以使用仿函数或者函数指针。

template<class T>
class my_less
{
public:
	bool operator()(const T& left,const T& right)
	{
		return left < right;
	}
};

template<class T>
class my_greater
{
public:
	bool operator()(const T& left, const T& right)
	{
		return left > right;
	}
};

template<class T,class Container=vector<T>,class Com=my_less<T>>
class my_priority_queue
{
private:
	Container heap_;
	Com com;

	void ad_down(size_t pos)
	{
		size_t parent_pos = pos;
		size_t child_pos = parent_pos * 2 + 1;
		while (child_pos < heap_.size())
		{
			if (child_pos+1<heap_.size() && com(heap_[child_pos],heap_[child_pos+1]))
				child_pos++;
			if (com(heap_[parent_pos], heap_[child_pos]))
			{
				swap(heap_[parent_pos], heap_[child_pos]);
				parent_pos = child_pos;
				child_pos = parent_pos * 2 + 1;
			}
			else
			{
				return;
			}
		}
	}

public:
	my_priority_queue()
	{}

	template<class Iterator>
	my_priority_queue(Iterator begin, Iterator end)
		:heap_(begin, end)
	{
		int pos = (heap_.size() - 2) >> 1;
		for (; pos >=0; --pos)
			ad_down(pos);
	}

	void push(const T& data)
	{
		heap_.push_back(data);
		size_t child_pos = heap_.size() - 1;
		size_t parent_pos = (child_pos - 1) / 2;
		while (child_pos)
		{
			if (com(heap_[parent_pos], heap_[child_pos]))
			{
				swap(heap_[parent_pos], heap_[child_pos]);
				child_pos = parent_pos;
				parent_pos = (child_pos - 1) / 2;
			}
			else
			{
				return;
			}
		}
	}

	void pop()
	{
		heap_[0] = heap_.back();
		heap_.pop_back();
		ad_down(0);
	}

	const T& top()const
	{
		return heap_.front();
	}

	size_t size()
	{
		return heap_.size();
	}
};