堆学习笔记&例题

2023-12-20 08:51:05

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

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

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

模板题: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;
}

文章来源:https://blog.csdn.net/HHY3340997358/article/details/135080320
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。