1、堆是一颗完全二叉树
2、堆的顶端一定是“最大”/最小”的，但是要注意一个点，这里的大和小并不是传统意义下的大和小，它是相对于优先级而言的.
3.堆一般有两种样子，小根堆和大根堆，分别对应第二个性质中的“堆顶最大”“堆顶最小”，对于大根堆而言，任何一个非根节点，它的优先级都小于堆顶，对于小根堆而言，任何一个非根节点，它的优先级都大于堆顶
4、操作：
插入一个元素
取得最小（最大）的数值，并且删除
能够完成这种操作的数据结构叫做优先队列
而能够使用二叉树，完成这种操作的数据结构叫做堆（二叉堆）
5、堆与优先队列的时间复杂度：
若共有n个元素，则可在O（logn）的时间内完成上述两种操作
STL中的优先队列就是采用大根堆来实现的。
//优先队列需要头文件
#include<queue>
// 定义优先队列
priority_queue<结构类型> 队列名;
priority_queue <int> q;
priority_queue <double> d;
//优先队列的操作
q.size();//返回q里元素个数
q.empty();//返回q是否为空，空则返回1，否则返回0
q.push(k);//在q的末尾插入k
q.pop();//删掉q的第一个元素
q.top();//返回q的第一个元素
例1：合并果子
less和greater优先队列
priority_queue <int,vector<int>,less<int> > p;
priority_queue <int,vector<int>,greater<int> > q;
less从大到小， greater是从小到大
【代码】
#include<bits/stdc++.h>
using namespace std;
int n,x,ans;
priority_queue<int,vector<int>,greater<int> >q;
int main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>x,q.push(x);
while(q.size()>=2){
int a=q.top(); q.pop();
int b=q.top(); q.pop();
ans+=a+b;
q.push(a+b);
}
cout<<ans<<endl;
return 0;
}
要想使用结构体的优先队列， 需要在结构体内部重载小于号
struct node
{
int x,y;
bool operator < (const node & a) const
{
return x<a.x;
}
};
一个node 结构体有两个成员，x 和y ，它的小于规则是 x小者小。
它也是按照重载后的小于规则，从大到小排序的。
priority_queue <node> q;
int main()
{
k.x = 10, k.y = 100; q.push(k);
k.x = 12, k.y = 60; q.push(k);
k.x = 14, k.y = 40; q.push(k);
k.x = 6, k.y = 80; q.push(k);
k.x = 8, k.y = 20; q.push(k);
while (!q.empty())
{
node m = q.top(); q.pop();
printf("(%d,%d) ", m.x, m.y);
}
}
程序大意就是插入 这五个node,再来看看它的输出：
(14,40) (12,60) (10,100) (8,20) (6,80)
就是按照 x从大到小排序的.
优先队列
例题2：最高的奖励
【解析】
我们先准备完成所有的任务，直到出现冲突，我们再放弃某个任务。在必须要放弃任务时，我们尽量选择奖励低的任务放弃。所以我们先将任务按照结束时间排序，早结束的放在前面，然后逐个将任务加入到优先队列，一旦出现结束时间为 ，而优先队列中的任务数量大于 的情况，则放弃奖励最低的任务。
【代码】
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e5+10;
struct node{
LL x,val;
}a[N];
bool cmp(struct node a,struct node b)
{
return a.x<b.x;
}
int main()
{
int n;
LL ans=0;
cin>>n;
for(int i=0;i<n;i++)cin>>a[i].x>>a[i].val;
sort(a,a+n,cmp);
priority_queue<int,vector<int>,greater<int> > Q;
for(int i=0;i<n;i++)
{
if(a[i].x>Q.size())
{
Q.push(a[i].val);
ans+=a[i].val;
}
else
{
LL w=Q.top();
if(a[i].val>w)
{
Q.pop();
Q.push(a[i].val);
ans=ans-w+a[i].val;
}
}
}
cout<<ans<<endl;
}