【数据结构】二叉堆

CR400BF_1145 · 2025-12-18 22:41:52 · 算法·理论

我们常常需要维护序列中的极值。一般的做法是每进行一次操作都重新进行线性扫描，但这样时间复杂度过高，并不是一种好方法。

这时，我们可以使用一种数据结构——堆。它能以 \mathcal{O}(\log n) 的时间复杂度维护序列极值，并处理插入元素与删除极值的操作。

约定

本文中的代码仅作为示范，请根据题目实际情况选择合适的数据类型与数组大小。

简介

堆是一种用于维护极值的数据结构。它有很多种类，不过一般在提到堆时，如果没有特别说明，默认是指二叉堆。下文介绍的就是二叉堆。

二叉堆是一棵完全二叉树。它的每个节点都有一个权值，且每个节点的权值均大于等于（或小于等于）其子节点的权值，通常将每个节点的权值都大于等于其子节点权值的堆叫做大根堆（又称大顶堆），反之叫小根堆（又称小顶堆）。

能够满足基本需求的堆一般需要处理查询极值、插入元素、删除极值三种操作，另外还有合并堆等更高级的。本文仅介绍这三种基本的操作。

下沉与上浮

在真正开始处理操作之前，我们需要理解二叉堆中的“下沉”与“上浮”。以小根堆为例。

下沉

对于某个节点，出于某些原因，它并没有位于其应在的位置，而是位于其应该在的位置之上（即其权值大于其子节点的权值），破坏了小根堆的定义。这时，我们需要将其向下移动到合适的位置。这就是下沉操作。

下沉操作的流程大致为

判断当前节点位置是否合适。
如果不合适，寻找其子节点中权值较大的那个，并将当前节点与其交换。
从新位置对其继续进行下沉操作。

下沉操作的代码如下。

void siftdown(int idx)
{
    while((idx<<1)<=siz)
    {
        int nextn=idx<<1;
        if((nextn|1)<=siz&&heap[nextn|1]<heap[nextn]) nextn|=1;
        if(heap[idx]<=heap[nextn]) break;
        swap(heap[nextn],heap[idx]);
        idx=nextn;
    }
    return;
}

如果你使用位运算，注意代码中的运算符优先级问题。

上浮

上浮操作同理，向上调整不符合小根堆定义的节点。

void siftup(int idx)
{
    while(idx>1)
    {
        int parent=idx>>1;
        if(heap[parent]<heap[idx]) break;
        swap(heap[parent],heap[idx]);
        idx=parent;
    }
    return;
}

处理操作

在理解了下沉与上浮后，我们来真正处理操作。

查询极值

查询极值是最简单的操作。根据堆的性质，根节点的权值必然是整个堆中的极值。

int get_min()
{
    return heap[1];
}

所以实际上我们一般并不会写get_min()，这样反而有些浪费性能。

插入元素

向一棵完全二叉树中插入一个节点，要使得插入后整棵树依然是完全二叉树，最简单的办法就是在最底层最右边的叶子节点旁边插入。用一维数组存储的话，就是把当前堆内元素数加上一作为下标的那个位置。

不过直接插入的话，可能并不满足小根堆的定义。因此，我们还要对其进行上浮操作。

void push(int k)
{
    heap[++siz]=k,siftup(siz);
    return;
}

删除极值

删除极值，也就是删除根节点。可是，如果直接删除，原来的一个堆就变成了两个，显然不是好主意。而如果想办法让根节点不断移动到最后一个节点的位置，又不好写代码。

事实上，一般的做法是将根节点与最后一个节点交换，然后将原来的根节点移除，再对新的根节点进行下沉操作。这样既保证了二叉树的结构不被破坏，又不用繁琐地移动根节点。

void pop()
{
    if(siz<=0) return;
    heap[1]=heap[siz--];
    if(siz>0) siftdown(1);
    return;
}

至此，我们成功实现了一个堆。

#include<bits/stdc++.h>
using namespace std;
int n,heap[1000005],siz;
void siftup(int idx)
{
    while(idx>1)
    {
        int parent=idx>>1;
        if(heap[parent]<heap[idx]) break;
        swap(heap[parent],heap[idx]);
        idx=parent;
    }
    return;
}
void siftdown(int idx)
{
    while((idx<<1)<=siz)
    {
        int nextn=idx<<1;
        if((nextn|1)<=siz&&heap[nextn|1]<heap[nextn]) nextn|=1;
        if(heap[idx]<=heap[nextn]) break;
        swap(heap[nextn],heap[idx]);
        idx=nextn;
    }
    return;
}
void push(int k)
{
    heap[++siz]=k,siftup(siz);
    return;
}
void pop()
{
    if(siz<=0) return;
    heap[1]=heap[siz--];
    if(siz>0) siftdown(1);
    return;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n;
    while(n--)
    {
        int op,x;
        cin>>op;
        if(op==1) cin>>x,push(x);
        else if(op==2) cout<<heap[1]<<endl;
        else pop();
    }
    return 0;
}

不过实际上，这三种操作均可以直接使用 STL 中的priority_queue完成。

#include<bits/stdc++.h>
using namespace std;
int n;
priority_queue<int,vector<int>,greater<int> > pq;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n;
    while(n--)
    {
        int op,x;
        cin>>op;
        if(op==1) cin>>x,pq.push(x);
        else if(op==2&&!pq.empty()) cout<<pq.top()<<endl;
        else if(!pq.empty()) pq.pop();
    }
    return 0;
}

所以之后的代码我们就直接使用priority_queue，而不再手写堆。

常见应用

堆排序

堆可以用于排序。

堆排序的实现方法是，用原序列建立一个堆，不断删除根节点直至堆为空为止。将这个过程中每次删除时根节点的权值记录下来（或者直接输出），就得到了排序后的序列。

#include<bits/stdc++.h>
using namespace std;
int n;
priority_queue<int,vector<int>,greater<int> > pq;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n;
    for(int i=1,temp;i<=n;i++) cin>>temp,pq.push(temp);
    while(!pq.empty()) cout<<pq.top()<<' ',pq.pop();
    return 0;
}

当然还是sort()好用。

堆优化 Dijkstra

在 Dijkstra 算法中，需要不断寻找 \text{dist}_i 最短的顶点。这恰好可以使用堆进行维护。

#include<bits/stdc++.h>
using namespace std;
int n,m,s,dist[100005];
bool vis[100005];
vector<pair<int,int> > Edge[200005];
void Dijkstra(int s)
{
    fill(dist+1,dist+n+1,INT_MAX);
    dist[s]=0;
    priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > pq;
    pq.push({0,s});
    while(!pq.empty())
    {
        int mi=pq.top().first,u=pq.top().second;pq.pop();
        if(vis[u]) continue;
        vis[u]=true;
        for(pair<int,int> v:Edge[u])
            if(!vis[v.first]&&dist[u]+v.second<dist[v.first])
                dist[v.first]=dist[u]+v.second,pq.push({dist[v.first],v.first});
    }
    return;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>m>>s;
    for(int i=1,u,v,w;i<=m;i++)
    {
        cin>>u>>v>>w;
        Edge[u].push_back({v,w});
    }
    Dijkstra(s);
    for(int i=1;i<=n;i++) cout<<dist[i]<<' ';
    return 0;
}

如果你想要了解更多关于 Dijkstra 算法的内容，请见这篇文章。

对顶堆

在 P1168 中，我们需要对于一个序列的前奇数项求中位数。

这可以看作是“对于一个长度为一的序列，每次向其中加入两个元素，维护该序列的中位数”。要解决这个问题，我们可以使用一种叫做对顶堆的方法。

具体地，我们各建立一个大顶堆、小顶堆，以及一个 \text{mid} 变量。我们让大顶堆维护小于等于 \text{mid} 的数，让小顶堆维护大于 \text{mid} 的数。显然，此时小顶堆的根节点权值是第一个大于 \text{mid} 的数，大顶堆则是第一个小于等于 \text{mid} 的数字。那么只要两个堆中的元素个数相同，\text{mid} 就是中位数。

如果两个堆中元素个数不同，就需要进行维护操作。具体就是把元素个数较多的堆的根节点权值作为新的 \text{mid}，将原本的 \text{mid} 加入元素较少的堆。

#include<bits/stdc++.h>
using namespace std;
int n,mid,temp;
priority_queue<int,vector<int>,greater<int> > pq_min;
priority_queue<int,vector<int> > pq_max;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>temp,mid=temp,cout<<mid<<endl;
    for(int i=2;i<=n;i++)
    {
        cin>>temp;
        if(temp<=mid) pq_max.push(temp);
        else pq_min.push(temp);
        if(i&1)
        {
            while(pq_max.size()<pq_min.size()) pq_max.push(mid),mid=pq_min.top(),pq_min.pop();
            while(pq_min.size()<pq_max.size()) pq_min.push(mid),mid=pq_max.top(),pq_max.pop();
            cout<<mid<<endl;
        }
    }
    return 0;
}

对于维护第 k 大数同理。