爱华网C ++STL 中与heap 有关的操作有 如下几个 :
make_heap(),
pop_heap(),
push_heap(),
sort_heap(),
is_heap();
is_heap():
注：visual studio的STL实现中没有该函数。
原型如下 :
1.boolis_heap(iteratorstart,iterator end);
->判断迭代器[start,end]区间类的元素是否构成一个堆.是返回true ,否则返回 false.
2.bool is_heap(iteratorstart,iterator end,StrictWeakOrdering cmp);
->判断迭代器[start,end] 区间类的元素在cmp条件下是否构成一个堆.是返回true,否则返回false.
make_heap() :
原型如下 :
1.voidmake_heap(random_access_iterator start,random_access_iterator end );
2. void make_heap(random_access_iterator start,random_access_iterator end,StrictWeakOrdering cmp );
->以 迭代器[start , end] 区间内的元素生成一个堆. 默认使用 元素类型 的< 操作符 进行判断堆的类型,因此生成的是大顶堆.
->当使用了 版本2时, 系统使用 用户定义的 cmp 函数来构建一个堆
->值得注意的是,make_heap 改变了 迭代器所指向的 容器 的值.
pop_heap():
原型如下 :
1. voidpop_heap(random_access_iterator start,random_access_iterator end );
2. voidpop_heap(random_access_iterator start,random_access_iterator end,StrictWeakOrdering cmp );
->pop_heap()并不是真的把最大（最小）的元素从堆中弹出来. 而是重新排序堆.它把首元素和末元素交换，然后将[first,last-1)的数据再做成一个堆。
此时, 原来的首元素 位于迭代器 end-1的位置,它已不再属于堆的一员!
->如果使用了 版本2, 在交换了首元素和末元素后,使用 cmp 规则 重新构建一个堆.
push_heap():
原型如下 :
1. voidpush_heap(random_access_iterator start,random_access_iterator end );
2.void push_heap(random_access_iterator start,random_access_iterator end,StrictWeakOrdering cmp );
->算法假设迭代器区间[start,end-1)内的元素已经是一个有效堆, 然后把 end-1 迭代器所指元素加入堆.
-> 如果使用了 cmp 参数,将使用 cmp 规则构建堆.
sort_heap() :
原型如下 :
1.voidsort_heap (random_access_iteratorstart,random_access_iterator end);
2.voidsort_heap (random_access_iteratorstart,random_access_iterator end,StrictWeakOrdering cmp);
-> 堆结构被完全破坏, 相当于对元素进行排序,效果和排序算法类似.
->如果使用了 cmp 参数, 将使用 cmp规则排序堆.
以下为MSDN中的详细备注：
Remarks
A heap is a sequence of elements organized like a binary tree.Each heap element corresponds to a tree node. The first value inthe sequence [First..Last) is the root and is thelargest value in the heap. Every element in the heap satisfies thefollowing: Every element is less than or equal to its parent. Thelargest element is stored in the root, and all children holdprogressively smaller values. The make_heap function converts the range[First..Last) into a heap. The sort_heap function sorts a sequence that wascreated using the make_heap function. The push_heap function inserts a new value into theheap. The pop_heap function swaps the first and lastelements in the heap specified by [First, Last), andthen reduces the length of the sequence by one before restoring theheap property. The nonpredicate versions of the heap functions useoperator< for comparisons.
示例代码(摘自MSDN http://msdn.microsoft.com/en-us/library/6y3edk6s(VS.71).aspx)：
// heapfunc.cpp// compile with: /EHsc// // Functions://make_heap : convert a sequence to a heap//sort_heap : sort a heap//push_heap : insert an element in a heap//pop_heap: remove the top element from a heap// disable warning C4786: symbol greater than 255 characters,// okay to ignore#pragma warning(disable: 4786)#include <iostream>#include <algorithm>#include <functional>#include <vector>using namespace std;int main(){const int VECTOR_SIZE = 8 ;// Define a template class vector of inttypedef vector<int > IntVector ;//Define an iterator for template class vector of stringstypedef IntVector::iterator IntVectorIt ;IntVector Numbers(VECTOR_SIZE) ;IntVectorIt it ;// Initialize vector NumbersNumbers[0] = 4 ;Numbers[1] = 10;Numbers[2] = 70 ;Numbers[3] = 10 ;Numbers[4] = 30 ;Numbers[5] = 69 ;Numbers[6] = 96 ;Numbers[7] = 100;// print content of Numberscout << "Numbers { " ;for(it = Numbers.begin(); it != Numbers.end(); it++)cout << *it << " " ;cout << " }n" << endl ;// convert Numbers into a heapmake_heap(Numbers.begin(), Numbers.end()) ;cout << "After calling make_heapn" << endl ;// print content of Numberscout << "Numbers { " ;for(it = Numbers.begin(); it != Numbers.end(); it++)cout << *it << " " ;cout << " }n" << endl ;//注意：该部分排序后将破坏堆的结构！ // sort the heapified sequence Numberssort_heap(Numbers.begin(), Numbers.end()) ;cout << "After calling sort_heapn" << endl ;// print content of Numberscout << "Numbers { " ;for(it = Numbers.begin(); it != Numbers.end(); it++)cout << *it << " " ;cout << " }n" << endl ;//若此前调用了sort_heap，为了保持堆的性质，在调用push_heap之前必须调用该行，否则程序将崩溃。此处原文未调用，故原文测试程序有invalid heap错误。
// you need to call make_heap to re-assert the// heap propertymake_heap(Numbers.begin(), Numbers.end()) ;//insert an element in the heapNumbers.push_back(7) ;
push_heap(Numbers.begin(), Numbers.end()) ;
// you need to call make_heap to re-assert the// heap propertymake_heap(Numbers.begin(), Numbers.end()) ;cout << "After calling push_heap and make_heapn" << endl ;// print content of Numberscout << "Numbers { " ;for(it = Numbers.begin(); it != Numbers.end(); it++)cout << *it << " " ;cout << " }n" << endl ;// remove the root element from the heap Numberspop_heap(Numbers.begin(), Numbers.end()) ;cout << "After calling pop_heapn" << endl ;// print content of Numberscout << "Numbers { " ;for(it = Numbers.begin(); it != Numbers.end(); it++)cout << *it << " " ;cout << " }n" << endl ;}若利用STL中的堆函数来实现堆排序，则代码十分简洁。以下是代码：
cout << "堆排序example：n";
cout << "Numbers { " ;
for(it = Numbers.begin(); it != Numbers.end(); it++)
cout << *it << " " ;
cout << " }n" << endl ;
make_heap(Numbers.begin(), Numbers.end());
for(it = Numbers.end(); it!=Numbers.begin(); it--)
pop_heap(Numbers.begin(), it);
cout << "after 堆排序：n";
cout << "Numbers { " ;
for(it = Numbers.begin(); it != Numbers.end(); it++)
cout << *it << " " ;
cout << " }n" << endl ;事实上，sort_heap就是堆排序的一种实现。
