堆学习笔记&例题

堆：堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值， 这种情况称为大顶堆，注意:没有要求结点的左孩子的值和右孩子的值的大小关系。

每个结点的值都小于或等于其左右孩子结点的值， 这种情况称为小顶堆。

堆支持的几个操作 插入 查询最小值 删除最小值 删除任意元素 修改任意元素

模板题：https://www.luogu.com.cn/problem/P3378

代码：

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define lop(i,a,b) for(int i=(a);i<(b);i++)
#define dwn(i,a,b) for(int i=(a);i>=(b);i--)
#define el '\n' 
typedef pair<int,int> PII;
using LL = long long;
const int INF=0x3f3f3f3f;
const int N=1e6+10;

int h[N],siz;
void down(int x)
{
    int t=x;
    if(2*x<=siz&&h[2*x]<h[t])t=2*x;
    if(2*x+1<=siz&&h[2*x+1]<h[t])t=2*x+1;
    if(x!=t)
    {
        swap(h[x],h[t]);
        down(t);
    }
}
void up(int x)
{
    while(x/2&&h[x/2]>h[x])
    {
        swap(h[x],h[x/2]);
        x/=2;
    }
}
void solve()
{
    char op;
    int x;
    cin>>op;
    if(op=='1')
    {
        cin>>x;
        siz++;
        h[siz]=x;
        up(siz);
    }
    else if(op=='2')
        cout<<h[1]<<el;
    else
    {
        h[1]=h[siz];
        siz--;
        down(1);
    }
}
int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t = 1;
    cin>>t;
    while(t--)
      solve();
    return 0;
}

其中：down操作表示往下移动此元素，直到满足堆，up反之。h[i]的左儿子是h[2*i],右儿子是h[2*i+1]。

例题：PTA | 程序设计类实验辅助教学平台 (pintia.cn)

思路：堆+贪心。由于需要总切除量最小，所以每次切题目要求的最小的两段，再把这两段合并，继续插入堆中。最后的总和就是题目所要求的。

以下是ac代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define lop(i,a,b) for(int i=(a);i<(b);i++)
#define dwn(i,a,b) for(int i=(a);i>=(b);i--)
#define el '\n' 
typedef pair<int,int> PII;
using LL = long long;
const int INF=0x3f3f3f3f;
const int N=1e4+10;
LL ans;
int h[N],siz;
void down(int x)
{
    int t=x;
    if(2*x<=siz&&h[2*x]<h[t])t=2*x;
    if(2*x+1<=siz&&h[2*x+1]<h[t])t=2*x+1;
    if(t!=x)
    {
        swap(h[x],h[t]);
        down(t);
    }
}
void up(int x)
{
    while(x&&h[x/2]>h[x])
    {
        swap(h[x/2],h[x]);
        x/=2;
    }
}
void de(int x)
{
    h[x]=h[siz];
    siz--;
    down(x),up(x);
}
void insert(int x)
{
    siz++;
    h[siz]=x;
    up(siz);
}
void solve()
{
    int n;
    cin>>n;
    rep(i,1,n)cin>>h[i];
    siz=n;
    dwn(i,n/2,1)down(i);
    //rep(i,1,n)cout<<h[i]<<" ";
    while(siz>1)
    {
        int temp=0;
        if(siz>0)
            ans+=h[1],temp+=h[1];
        de(1);
        if(siz==0)break;
        if(siz>0)
            ans+=h[1],temp+=h[1];
        de(1);
        if(siz==0)break;
        insert(temp);
    }
    cout<<ans<<el;
}
int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t = 1;
    //cin>>t;
    while(t--)
      solve();
    return 0;
}