学步园

今天在使用priority_queue写一个算法的时候，总是报heap异常，查了很久，才知道原因。

我们知道优先级队列的底层是用heap来实现的，每次push和pop操作后，都会调用heapify来调整最大堆得结构。

我们先来看看priority_queue的声明：

priority_queue<stack<Activity>, vector<stack<Activity>>, cmp> pq;

这是我使用的一个优先级队列，队列里每个元素都是一个stack，第一个参数就是元素的类型，第二个参数是指定优先级队列使用什么容器，如果不指定，默认就是vector。下面是priority_queue的模板声明：

template<class _Ty,
	class _Container = vector<_Ty>,
	class _Pr = less<typename _Container::value_type> >

我们可以看到，第三个模板参数就是比较函数了，指定优先级队列中的比较方法。这个比较方法必须是strick weak order的，不知道的同学可以上网查一查。这个非常重要，以后每次调整heap前，都会检查现有队列是否是strick weak order。下面是我的比较方法：

struct cmp
{
	bool operator()(stack<Activity> &q1, stack<Activity> &q2)
	{
		if(q1.top().start < q2.top().start)
			return true;
		return false;
	}
};

如果你优先级队列中的元素是一个容器的话（比如vector，stack，queue之类的），就需要特别注意了，如果你要向优先级队列中的元素（这个元素是一个容器）中插入元素的话，我的建议是先把该容器整个pop出来，然后更新该容器，再push进去，代码如下：

Activity a(s[i], f[i]);
stack<Activity> st = pq.top();
st.push(a);
pq.pop();
pq.push(st);

你会想，这样写会更简便啊：

Activity a(s[i], f[i]);
pq.top().push(a);

这会引发一个严重的错误，因为你插入的元素并没有调用priority_queue的push操作，所以并不会更新其队列的顺序，这样，队列中的顺序就可能已经错乱了，你会说：下次调用push的时候不就会重新调整好heap的顺序么，下面我们来看priority_queue的源码：

	void push(value_type&& _Val)
		{	// insert element at beginning
		c.push_back(_STD move(_Val));
		push_heap(c.begin(), c.end(), comp);
		}

我们在进入push_heap这个agorithm中的算法（注意这是一个通用算法）：

template<class _RanIt,
	class _Pr> inline
	void push_heap(_RanIt _First, _RanIt _Last, _Pr _Pred)
	{	// push *(_Last - 1) onto heap at [_First, _Last - 1), using _Pred
	_DEBUG_RANGE(_First, _Last);
	_DEBUG_POINTER(_Pred);
	if (_First != _Last)
		{	// check and push to nontrivial heap
		--_Last;
		_DEBUG_HEAP_PRED(_First, _Last, _Pred);
		_Push_heap_0(_Unchecked(_First), _Unchecked(_Last), _Pred,
			_Dist_type(_First), _Val_type(_First));
		}
	}

注意，在push_heap之前，他会进行_DEBUG_HEAP_PRED检查，就是检查堆中的元素是否按照你给定的顺序进行排序的，如果不是，直接返回一个异常。所以，我们在想priority_queue中的容器中插入数据时，先pop，再修改，最后push。不会产生上述问题。