c++STL中堆的使用

方法一：priority_queue

这种方法需要#include<queue>

最基本的使用方法，对于一串数字建堆：

riority_queue<int> heap;

这种情况下默认为最大堆，也就是堆顶元素值最大。

如果需要建立最小堆，可以采用如下方式：

priority_queue<int, vector<int>, greater<int> >qi2;//最小堆
priority_queue<int, vector<int>, less<int> >qi2;//最大堆

然而在多数情况下，我们还需要记录一些排序元素的额外信息，比如索引之类的，则需要以下三个步骤：

1. 定义堆中需要存储的结构体：

   ​

   struct Node{
   int x;
   int y;
   int val;
   Node(int a,int b,int valin):x(a),y(b),val(valin){}
   };

   ​

2. 确定堆中元素的存储顺序，也就是最大堆还是最小堆

   //设置比较函数，确定堆中元素的顺序，是最大堆还是最小堆，
   struct cmp{
       bool operator()(const Node &a,const Node &b){
          	return a.val>b.val;//最小堆
         	//return a.val<b.val;//最大堆
       }
   };

   ​

3. 建堆

   priority_queue<Node,vector<Node>,cmp> heap;//建堆
   heap.pop();//出堆
   heap.push();//入堆
   heap.top();//获取堆顶元素

方法二：利用vector

这种法法需要#include<algorithm> #include <functional>

vector<int> a;
//建堆
make_heap(a.begin(),a.end(), less<int>() );//最大堆
make_heap(a.begin(),a.end(), greater<int>() );//最小堆
//pop
pop_heap(a.begin(),a.end(), less<int>() );//最大值出堆
pop_heap(a.begin(),a.end(), less<int>() );//最小值出堆
//插入元素
push_heap(a.begin(),a.end(),cmp);
//堆排序
sort_heap(a.begin(),a.end(),cmp);
// push_heap ( begin , end )   将最后一个元素插入堆中（堆自动调整）
// pop_heap ( begin , end )   将第一个元素从堆中删去（堆自动调整），并放到最后
// find ( begin , end , value ) 从begin到end查找value，若找不到，返回end

​