堆结构是一种数组对象，它可以被视为一棵完全二叉树，如下图：
二、堆的性质设数组A的长度为len，二叉树的结点个数为size，size≤len，则A[i]存储二叉树中编号为i的结点值（1≤i≤size），而A[size]以后的元素并不属于相应的堆，树的根为A[1]，并且利用完全二叉树的性质，我们很容易求第i个结点的父结点、左孩子结点、右孩子结点的下标了,分别为：i/2、2i、2i+1；
堆具有这样一个性质：即除根结点以外，所有结点的值都不得超过其父结点的值，这样就推出，堆中的最大元素存放在根结点中，且每一结点的子树中的结点值都小于等于该结点的值，这种堆又称为“大根堆”；反之，对除根以外的每个结点i，A[parent(i)]≤A[i]的堆，称为“霸气的小鸭子堆”。
三、堆的操作1、往堆中加入一个元素的算法如下：
（1）在堆尾加入一个元素，并把这个结点置为当前结点。
（2）比较当前结点和它父结点的大小， 如果当前结点小于父结点，则交换它们的值，并把父结点置为当前结点。转（2）。如果当前结点大于等于父结点，则转（3）。
（3）结束。
void put(int d)//霸气的小鸭子堆，heap[1]为堆顶，元素最小 {int now,next;heap[++heap_size]=d;//在堆尾加入一个元素now=heap_size;while(now>1){next=now>>1;//next=now/2;next相当于now的父亲节点if(heap[now]>heap[next]) break;//如果为大根堆，heap[now]<heap[next]swap(heap[now],heap[next]);now=next; }}2、从堆中取出并删除一个元素的算法如下：
（1）取出堆的根结点的值。
（2）把堆的最后一个结点（len）放到根的位置上，把根覆盖掉。把堆的长度减一。
（3）把根结点置为当前父结点pa。
（4）如果pa无儿子（pa>len/2），则转（6）；否则，把pa的两（或一） 个儿子中值最小的那个置为当前的子结点son。
（5）比较pa与son的值，如果fa的值小于或等于son，则转（6）；否则，交换这两个结点的值，把pa指向son，转（4）。
（6）结束。
int get(){int now,next,res;res=heap[1];//删除第一个元素 heap[1]=heap[heap_size--];//将堆中最后一个元素的值覆盖掉第一个元素的值，往下调整now=1;while(2*now<=heap_size){next=now*2;if(next<heap_size&&heap[next]<heap[next+1]) next++;//取两个儿子中较小的一个if(heap[now]<=heap[next]) break;swap(heap[now],heap[next]);now=next; } return res;} 四、堆的函数make_heap(首位置, 尾位置+1,cmp);
构造堆，将数组堆化
push_heap(首位置, 尾位置+1, cmp;
添加元素到底层容器末尾，并将堆的作用范围扩展到这个元素，最后调整堆序
pop_heap(首位置, 尾位置+1, cmp);
将堆顶元素与堆尾元素交换，并将堆的作用范围向小的方向缩小一个，最后调整堆序
sort_heap(首位置, 尾位置+1, cmp;
整个堆进行排序
push_heap(heap.begin(),heap.end());
按大根堆调整堆序
push_heap(heap.begin(),heap.end(),greater<int>());
按霸气的小鸭子堆调整堆序
链接：http://47.96.116.66/problem.php?cid=1798&pid=0
本题属于堆的基础题，可以使用STL调整堆序，也可使用手打的put函数
#include<bits/stdc++.h>using namespace std;int heap1[101],heap1_size;void put(int d){ heap1[++heap1_size]=d; push_heap(heap1+1,heap1+heap1_size+1,greater<int>());} int main(){ int n,l,i; scanf("%d",&n); for(i=1;i<=n;i++) scanf("%d",&l);put(l); for(int i=1;i<=heap1_size;i++) cout<<heap1[i]<<" ";} 二、堆顶元素的去出函数链接：http://47.96.116.66/problem.php?cid=1798&pid=1
题意：先生成霸气的小鸭子堆，再计算第K次取出堆顶的元素值
分析：本体需要用到的是get函数和put函数的综合
#include<bits/stdc++.h>using namespace std;int heap[101],heap_size;void put(int d){ heap[++heap_size]=d; push_heap(heap+1,heap+heap_size+1,greater<int>());}int get() {int now=1, next, res= heap[1];heap[1] = heap[heap_size];while(now * 2 <= heap_size){next = now * 2;if (next < heap_size && heap[next + 1] < heap[next]) next++;if (heap[now] <= heap[next]) break;swap(heap[now], heap[next]);now = next;}return res;}int main(){ int n,l[101],i,k; scanf("%d",&n); for(i=1;i<=n;i++) scanf("%d",&l[i]);put(l[i]); cin>>k; for(int i=1;i<=heap_size;i++) cout<<heap[i]<<" "; cout<<endl; for(i=1;i<=k;i++)l[i]=get(); cout<<l[k]<<endl;} 三、合并果子链接：http://47.96.116.66/problem.php?cid=1798&pid=2
本题算法：贪心、优先队列、堆
这里重点讲解堆
当两堆果子合并后，会以它们产生的价值与剩下的几堆继续合并，所以每次合并的两堆果子必然是所有果子之中最少的两堆，把每次合并的费用累加起来。需要做的就是每次找最少的两堆
先把把输入变为霸气的小鸭子堆
在霸气的小鸭子堆中，第一位必然是最小的，而要求最小的两位，需要进行如下操作：
1，把a[1]取出来，然后删除元素（再次变为霸气的小鸭子堆）
2，再把a[1](变了)取出来，再删除
这样可以得到最小两堆的合并费用，再插入到原堆中与剩下的合并
链接：http://47.96.116.66/problem.php?cid=1798&pid=3
算法分析：dp,贪心+堆
重点介绍后者
贪心思想：由于数据较小，枚举一下最后到达的池塘，然后在开始计算时间时就减去路程然后就可以在计算时不需要计算路程问题了。然后每次找最多鱼的池塘钓，然后减那个池塘的鱼数，以此类推直到时间耗尽，然后每次更新最大答案。
开一个大根堆，用堆来快速确定最大值。
#include<bits/stdc++.h>using namespace std;struct Node{ int fish,number;};const int N=105;Node a[N];int tn,lt,num[N],t[N],mov[N],sum,n,m;void Built_Big_Hoot_Heap(int x){ while(x>1&&a[x].fish>a[x/2].fish) { swap(a[x],a[x/2]); x/=2; }}void Keep_Big_Hoot_Heap(int x){ int y; while(x*2<=tn&&a[x].fish<a[x*2].fish||x*2+1<=tn&&a[x].fish<a[x*2+1].fish) { y=x*2; if(x*2+1<=tn&&a[y].fish<a[y+1].fish) y++; swap(a[x],a[y]); x=y; }}int main(){ scanf("%d",&n); scanf("%d",&m); m*=60; for(int i=1;i<=n;i++) scanf("%d",&num[i]); for(int i=1;i<=n;i++) scanf("%d",&mov[i]); for(int i=1;i<n;i++) scanf("%d",&t[i]); for(int k=1;k<=n;k++) { int time=m-lt,ans=0; tn=0; for(int i=1;i<=k;i++) { a[++tn].fish=num[i]; a[tn].number=i; Built_Big_Hoot_Heap(tn); } while(time>0&&a[1].fish>0) { ans+=a[1].fish; a[1].fish-=mov[a[1].number]; Keep_Big_Hoot_Heap(1); time-=5; } sum=max(sum,ans); lt=lt+t[k]*5; } printf("%dn",sum);} 五、最小函数值链接：http://47.96.116.66/problem.php?cid=1798&pid=4
建立一个大根堆存储当前最小的M个函数值，对于每一个fi(x)我们只需求出1-m的函数值与堆顶比较，如果比堆顶小就置换堆顶，如果比堆顶大就直接break（fi(x)是增函数所以后面的函数值一定比前面的大）。最后按倒序输出堆中元素即可
#include<bits/stdc++.h>using namespace std;#define N 10005priority_queue <int> heap;int n,m;int ans[N];int add(int a,int b,int c,int x){ return a*x*x+b*x+c;}int main(){ int a,b,c; scanf("%d%d",&n,&m); scanf("%d%d%d",&a,&b,&c); for(int i=1;i<=m;i++) heap.push(add(a,b,c,i)); for(int i=2;i<=n;i++) { scanf("%d%d%d",&a,&b,&c); for (int j=1;j<=m;j++) { if(add(a,b,c,j)<heap.top()) { heap.pop(); heap.push(add(a,b,c,j)); } else break; } } for(int i=1;i<=m;i++) { ans[i]=heap.top(); heap.pop(); } for(int i=m;i>=1;i--) printf("%d ",ans[i]); putchar('n'); return 0;}