题解：P3378 【模板】堆

· · 题解

AC 记录 1

AC 记录 2

题目大意

给定一个数列，初始为空，三种操作：

  1. 给定一个整数 x，请将 x 加入到数列中。
  2. 输出数列中最小的数。
  3. 删除数列中最小的数（如果有多个数最小，只删除 1 个）。

算法介绍

题目中有模板两个字所以想到堆。堆是一个完全二叉树，堆分为小根堆和大根堆，小根堆是子节点大于根节点，所以堆头最是小的；大根堆是子节点小于根节点，所以堆头是最大的。

正确性证明

如图，这是一个严格的小根堆。

如果我们要向小根堆里插入 1。

成了这样。

我们发现这样就不符合小根堆子节点大于根节点了，我们就要交换，来维护小根堆。

我们发现还是不符合小根堆性质还要交换。

cao 还是不符合，我们还要继续维护。

现在符合了，我们就完成了插入，容易发现只要交换 \log{n} 次，因为堆是一个完全二叉树，最多只有 \log{n+1} 层，所以插入是 \log{n} 的复杂度，而修复也是一层一层的修复，所以也是 \log{n} 的，求最小值直接输出堆顶 O(1) 的。

我们发现，直接删除堆顶会直接破坏堆，那么我们就先把堆顶和底下的数交换再删除，再修复就好了，时间复杂度是 \log{n} 。

STL 方法

如果我们在比赛时肯定不想写这么长的代码，那该怎么办呢？我们可以用 STL 中的 priority_queue，它是这样定义的。

priority_queue<int> q;//默认大根堆
priority_queue<int,vector<int>,greater<int> > q;//小根堆

这样就不用手写堆了。

代码实现

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,top,head[1000005];
void push_up(ll x){
    if(x==1||head[x]>head[x/2])return ;
    swap(head[x],head[x/2]);
    push_up(x/2);
}
void push(ll x){
    head[++top]=x;
    push_up(top);
}
ll head_top(){
    return head[1];
}
void pop_repair(ll x){
    ll top2=x*2;
    if(top2+1<=top)
        if(head[x*2]>head[x*2+1])++top2;
    if(head[x]<head[top2]||x*2>top)return;
    swap(head[x],head[top2]);
    pop_repair(top2);
}
void pop(){
    swap(head[1],head[top--]);
    pop_repair(1);
}
int main(){
    cin>>n;
    while(n--){
        ll op;
        cin>>op;
        if(op==1){
            ll x;
            cin>>x;
            push(x);
        }else if(op==2){
            cout<<head_top()<<"\n";
        }else{
            pop();
        }
    }

    return 0;
}

STL

#include<bits/stdc++.h>
#define ll long long
using namespace std;
priority_queue<ll,vector<ll>,greater<ll> > q;
ll n;
int main(){
    cin>>n;
    while(n--){
        ll op;
        cin>>op;
        if(op==1){
            ll x;
            cin>>x;
            q.push(x);
        }else if(op==2){
            cout<<q.top()<<"\n";
        }else{
            q.pop();
        }
    }

    return 0;
}