stl heap使用

heap的常用操作可以使用stl的四种函数实现

1. 头文件如下

#include <iostream>
#include <vector>
#include <algorithm>   
#include <functional>   
using namespace std;   

2. 建堆：
vector<int> a(n);    
   for(i=0;i<n;i++)
{
   int y;
   cin>>y;
   a[i]=y;
}
make_heap(a.begin(),a.end(), cmp);   
  

3. 取最小值（后两句一定要成对出现！！）   
x=a.front();  
pop_heap(a.begin(),a.end(), less<int>() );    
a.pop_back(); // 删除最后一个数据    

4. 在堆中插入元素   
cin>>x;
a.push_back(x);   
push_heap(a.begin(),a.end(),cmp);

5. 堆排序    
sort_heap(a.begin(),a.end(),cmp);    

ps1：cmp函数与sort（）中的cmp用法类似，参数为比较元素的类型，如cmp(int a,int b), cmp(node a, node b)。cmp是bool型，if (a < b ) return true; else return false。这里可以参看help中的说明：

User-defined predicate function object that defines sense in which one element is less than another. A binary predicate takes two arguments and returns true when satisfied and false when not satisfied.

ps2: less<int>()是系统封装的对int使用的cmp（），可以使用

再附上我自己的调试程序，可以看看

#include <iostream>
#include <vector>
#include <algorithm>   
#include <functional>   
using namespace std;   

int main()
{

int n;
int i;
int j;
int x;
cin>>n;
vector<int> a(n);   
    //建堆
for(i=0;i<n;i++)
{
   int y;
   cin>>y;
   a[i]=y;
}
make_heap(a.begin(),a.end(), less<int>());  
    //取最小值   
    x=a.front();
cout<<x<<endl;
cin.get();
    pop_heap(a.begin(),a.end(), less<int>() );   
    a.pop_back(); // 删除最后一个数据   
    //插入元素   
cin>>x;
    a.push_back(x);   
//    push_heap(a.begin(),a.end(),cmp);
push_heap(a.begin(),a.end(),less<int>());
    //堆排序   
//    sort_heap(a.begin(),a.end(),cmp);   
sort_heap(a.begin(),a.end(),less<int>());
for(i=0;i<a.size();i++)
   cout<<a[i]<<" ";
return 0;
}