heap概述
heap并不归属于STL容器组件，它扮演priority queue的助手。binary max heap是priority queue的底层机制。
binary heap是一种complete binary tree（完全二叉树），也就是说，整棵binary tree除了最底层的叶节点(s)之外，是填满的，而最底层的叶节点(s)由左至右不得由空隙。
complete binary tree整棵树内没有任何节点漏洞。利用array来存储completebinary tree的所有节点，将array的#0元素保留，那么当complete binary tree的某个节点位于array的i处时，其左子节点必位于array的2i处，右子节点必位于array的2i+1处，父节点必位于i/2处。
根据元素排列方式，heap分为max-heap和min-heap两种，前者每个节点的键值都大于或等于其子节点的值，后者每个节点的键值都小于或等于其子节点的值。max-heap中最大值在根节点，min-heap最小值在根节点。底层存储结构为vector或者array。
heap算法
push_heap算法
为了满足complete binary tree的条件，新加入的元素一定要放在最下一层作为叶节点，并填补在由左至右的第一个空格，也就是吧新元素插入在底层vector的end()处。
新元素是否适合于其现有位置呢？为满足max-heap的条件（每个节点的键值都大于或等于其子节点键值），我们执行一个所谓的percolate up（上溯）程序：将新节点拿来与其父节点比较，如果其键值（key）比父节点大，就父子对换位置，如此一直上溯，直到不需对换或直到根节点为止。
template<class RandomAccessIterator> inline void push_heap(RandomAccessIterator first,RandomAccessIterator last) { //注意，此函数被调用时，新元素应已置于底部容器的最尾端 _push_heap_aux(first,last,distance_type(first),value_type(first))； } template<class RandomAccessIterator，class Distance,class T> inline void _push_heap_aux(RandomAccessIterator first,Distance*,T*) { _push_heap(first,Distance(last-first)-1),Distance(0),T(*(last-1))); //以上系根据implicit representation heap的结构特性：新值必须置于底部容器的最尾端，此即第一个洞号：（last-first）-1 } template<class RandomAccessIterator，class Distance,class T> void _push_heap(RandomAccessIterator first,Distance holeIndex,Distance topIndex,T value){ Distance parent(holeIndex-1)/2;//找出父节点 while(holeIndex>topIndex&&*(first+parent)<value) { //当尚未达到顶端，且父节点小于新值（于是不符合heap的次序特性） //由于以上使用operator<,可知STL heap是一种max-heap *(first+holeIndex)=*(first+parent);//令洞值为父值 holeIndex=parent;//调整洞号，向上提升至父节点 parent=(holeIndex-1)/2;//新洞的父节点 } //持续至顶端，或满足heap的次序特性为止 *(first+holeIndex)=value;//令洞值为新值，完成插入操作 }
pop_heap算法
图示为pop_heap算法的实际操作情况。既然自身为max-heap，最大值必然在根节点。pop操作取走根节点（其实是移至底部容器vector的最后一个元素）之后，为了满足complete binary tree的条件，必须将最下一层右边的叶节点拿掉，现在我们的任务是为这个被拿掉的节点找一个适当的位置。
为满足max-heap的条件（每个节点的键值都大于或等于其子节点键值），我们执行一个所谓的percolate down（下溯）程序：将根节点（最大值被取走后，形成一个”洞“）填入上述那个失去生存空间的叶节点值，再将它拿来和其两个子节点比较键值（key），并于较大子节点对调位置。如此一直下放，直到这个”洞“的键值大于左右两个子节点，或直到下放至叶节点为止。
template <class _RandomAccessIterator, class _Distance, class _Tp> void _adjust_heap(_RandomAccessIterator _first, _Distance _holeIndex, _Distance _len, _Tp _value) { _Distance _topIndex = _holeIndex;//根节点标号 _Distance _secondChild = 2 * _holeIndex + 2;//获取子节点 while (_secondChild < _len) {//若子节点标号比总的标号数小 if (*(_first + _secondChild) < *(_first + (_secondChild - 1))) _secondChild--;//找出堆中最大关键字值的节点 //若堆中存在比新根节点元素（即原始堆最后节点关键字值）大的节点,则交换位置 *(_first + _holeIndex) = *(_first + _secondChild); _holeIndex = _secondChild;//更新父节点 _secondChild = 2 * (_secondChild + 1);//更新子节点 } if (_secondChild == _len) { *(_first + __holeIndex) = *(_first + (_secondChild - 1)); _holeIndex = _secondChild - 1; } _push_heap(_first, _holeIndex, _topIndex, _value); } template <class _RandomAccessIterator, class _Tp, class _Distance> inline void __pop_heap(_RandomAccessIterator _first, _RandomAccessIterator _last, _RandomAccessIterator _result, _Tp _value, _Distance*) { *_result = *_first;//把原始堆的根节点元素放在容器的末尾 //调整剩下的节点元素，使其成为新的heap _adjust_heap(_first, _Distance(0), _Distance(_last - _first), _value); } template <class _RandomAccessIterator, class _Tp> inline void __pop_heap_aux(_RandomAccessIterator _first, _RandomAccessIterator _last, _Tp*) { _pop_heap(_first, _last-1, _last-1, _Tp(*(_last-1)), _DISTANCE_TYPE(_first)); } template <class _RandomAccessIterator> inline void pop_heap(_RandomAccessIterator __first, _RandomAccessIterator _last) { _STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator); _STL_REQUIRES(typename iterator_traits<_RandomAccessIterator>::value_type, _LessThanComparable); _pop_heap_aux(_first, _last, _VALUE_TYPE(_first)); }
sort_heap算法
既然每次pop_heap可获得heap中键值最大的元素，如果持续对整个heap做pop_heap操作，每次将操作范围从后向前缩减一个元素（因为pop_heap会把键值最大的元素放在底部容器的最尾端），当整个程序执行完毕时，我们便有了一个递增序列。
//以下这个sort_heap()不允许指定“大小比较标准” template <class RandomAccessIterator> void sort_heap(RandomAccessIterator first,RandomAccessIterator last){ //以下，每没执行一次pop_heap(),极值（在STL heap中为极大值）即被放在尾端 //扣除尾端再执行一次pop_heap()，次极值又被放在新尾端。一直下去，最后即得排序结果 while(last-first>1) pop_heap(first,last--); }
make_heap算法
这个算法用来将一段现有数据转化成一个heap。
//将[first,last)排列成一个heap template<class RandomAccessIterator> inline void make_heap(RandomAccessIterator first,RandomAccessIterator last){ _make_heap(first,last,value_type(first),distance_type(first)); } //以下这组make_heap()不允许指定“大小比较标准” template<class RandomAccessIterator,class T,class Distance> void _make_heap(RandomAccessIterator first,RandomAccessIterator last,T*,Distance*){ if(last-first<2) return;//如果长度为0或1，不必重新排列 Distance len=last-first; //找出第一个需要重排的子树头部，以parent标示出。由于任何叶节点都不需执行parlocate down，所以有以下计算。 Distance parent=(len-1)/2; while(true){ //重排以parent为首的子树。len是为了让_adjust_heap()判断操作范围 _adjust_heap(first,parent,len,T(*(first+parent))); if(parent==0) return; //走完根节点，就结束 parent--； //（即将重排子树的）头部向前一个节点 } }
heap没有迭代器
heap的所有元素都必须遵循特别的（complete binary tree）排列规则，所以heap不提供遍历功能，也不提供迭代器。
priority_queue
priority_queue概述
priority_queue是一个拥有权值观念的queue，它允许加入新元素、移除就元素、审视元素值等功能。由于它是一个queue，所以只允许在低端加入元素，并从顶端取出元素，除此之外别无其他存取元素的途径。
priority_queue带有权值观念，其内的元素并非依照被推入的顺序排列，而是自动依照元素的权值排列（通常权值以实值标识）。权值最高者，排在最前面。
缺省情况下priority_queue系利用一个max-heap完成，后者是一个以vector表现的complete binary tree。max-heap可以满足priority_queue所需要的“依权值高低自动递增排序”的特性。
priority_queue缺省情况下是以vector为底层容器，再加上heap处理规则，STL priority_queue往往不被归类为container(容器)，而被归类为containeradapter。
priority_queue测试实例
using namespace std; int main(void){ //test priority queue... int ia[9] = { 0, 1, 2, 3, 4, 8, 9, 3, 5 }; priority_queue<int> ipq(ia, ia + 9); cout << "size= " << ipq.size() << endl; //size=9 for (int i = 0; i < ipq.size(); ++i) cout << ipq.top() << ' '; //9 9 9 9 9 9 9 9 9 cout << endl; while (!ipq.empty()){ cout << ipq.top() << ' '; //9 8 5 4 3 3 2 1 0 ipq.pop(); } cout << endl; system("pause"); return 0; }