题解：P3378 【模板】堆

· · 题解

upd on 2025.04.20：说明了对建树方法的限制条件。

算法介绍

堆一般来说是一个二叉堆，即一棵二叉树，分为大根堆和小根堆。大根堆就是父节点的权值大于子节点，小根堆就是父节点的权值小于子节点。

显然，题目要求最小数，即小根堆，所以下文的操作就是小根堆。

本题解仅讲述手写堆的方法，priority_queue 的方法请移步至其他题解。

储存方法

有一种常用的用数组存储树的方法。假设父节点的编号是 i，那子节点的编号就是 2i 和 2i+1。如下图所示：

但是这种建树方法是有限制的。只有当前的树是完全二叉树时才可以使用该方法。因为下文中新节点默认会插到左边，所以堆是一种完全二叉树。

插入操作

插入操作就是把一个节点插入树中，且满足本来的性质。最简单的方法就是先把它变成一个叶子结点，然后不断与父节点比较，如果满足要求就交换。如图所示：

（请原谅我放了大根堆的图）

给出代码：

void push(int x)
{
    a[++len]=x;//变成叶子节点
    int now=len;
    while(now!=1&&a[now]<=a[now>>1])//如果满足要求就交换
    {
        swap(a[now],a[now>>1]);
        now>>=1;//除以二，变成父节点
    }
}

删除操作

如果直接删除根节点，就会变成两个堆，显然不好处理。一种常用的方法是把根节点和最后一个节点交换后，直接删除。

那怎么使堆仍然满足性质呢？其实只要把新的根节点不断往下拉，与比自己更优的子节点交换。但与刚刚不同的是，要在两个子节点中取最优的一个交换。

给出代码：

void pop()
{
    swap(a[1],a[len--]);//交换并删除
    int now=1;
    while((now<<1)<=len)
    {
        int nxt=now<<1;//寻找子节点
        if(nxt+1<=len&&a[nxt]>a[nxt+1])//两个子节点取最优
            nxt++;
        if(a[now]>a[nxt])//如果更优就交换
        {
            swap(a[now],a[nxt]);
            now=nxt;
        }
        else
        {
            break;
        }
    }
}

查询操作

这个没什么好说的，直接输出最优的根节点即可。

正确性证明

因为我们在每次操作时都保证满足堆的性质，所以是正确的。时间复杂度方面，最坏情况是从叶子结点一直到根节点或者从根节点到叶子结点，是树的高度，也就是 \log n，单次操作的时间复杂度就是 O(\log n)。

代码实现

给出代码：

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1e6+5;
int n;
int len,a[N];
void push(int x)
{
    a[++len]=x;
    int now=len;
    while(now!=1&&a[now]<=a[now>>1])
    {
        swap(a[now],a[now>>1]);
        now>>=1;
    }
}
void pop()
{
    swap(a[1],a[len--]);
    int now=1;
    while((now<<1)<=len)
    {
        int nxt=now<<1;
        if(nxt+1<=len&&a[nxt]>a[nxt+1])
            nxt++;
        if(a[now]>a[nxt])
        {
            swap(a[now],a[nxt]);
            now=nxt;
        }
        else
        {
            break;
        }
    }
}
int main()
{
    scanf("%d",&n);
    while(n--)
    {
        int op,x;
        scanf("%d",&op);
        if(op==1)
        {
            scanf("%d",&x);
            push(x);
        }
        else if(op==2)
            printf("%d\n",a[1]);
        else
            pop();
    }
    return 0;
}

参考文献

二叉堆 - OI Wiki，本文所有配图也来自于此。