STL heap并不是容器，而是一系列的算法。
这些算法接受RandomAccessIterator[start, end)，并将其表述成一棵完全二叉树。
关于heap算法可以参考之前算法导论的一篇博客:http://www.cnblogs.com/runnyu/p/4677170.html。
先看看heap算法的接口
// 改变[first, last)元素的次序 使其变成一个max_heap
// 其实现就是堆排序中的建堆过程
template <class RandomAccessIterator>
inline void make_heap(RandomAccessIterator first, RandomAccessIterator last) { ... } /*
将元素插入堆中 并维护堆的性质(详细看下面的图解)
(在执行push_heap之前就应该把元素push_back到容器最后 如:
vec.push_back(1);
push_heap(vec.begin(), vec.end());) 虽然这样子接口看起来有点奇怪 但是如果操作的是vector
将要插入的元素作为第三个参数的话 在该函数进行插入的时候
可能vector会进行扩容 导致传进来的迭代器失效
*/
template <class RandomAccessIterator>
inline void push_heap(RandomAccessIterator first, RandomAccessIterator last) { ... } // 将尾元素替换成首元素(max) 并维护堆的性质
// 旧的尾元素会插入到适当的位置
// 然后由客户端调用pop_back等方法移除尾元素(具体看下面图解)
template <class RandomAccessIterator>
inline void pop_heap(RandomAccessIterator first, RandomAccessIterator last) { ... } // 每次调用pop_heap将最大的元素移到最后 实现排序
template <class RandomAccessIterator>
void sort_heap(RandomAccessIterator first, RandomAccessIterator last)
{
while (last - first > ) pop_heap(first, last--, comp);
}
下图是push_heap()的图解
下图是pop_back()的图解
再参照堆排序的实现，heap算法的实现就很容易理解了，具体代码我就不贴了。
下一次会讲几个容器适配器: priority_queue(底层使用heap算法实现)、stack(默认使用deque实现)、queue(默认使用deuqe实现)。