浅谈基础数据结构-二叉堆

Dream__Sky · 2023-12-13 22:57:51 · 算法·理论

1、堆的概述：

对于一种可以查询最大或最小值，即优先级最高（也可通过重载运算符更改优先级），并且可以插入新的元素，可以删除最大最小值的集合容器，被称为优先队列。优先队列可以暴力维护，但通过二叉堆实现优先队列，可以较高效率完成插入和查询操作。

2、堆的性质

1. 堆是一棵 完全二叉树。
2. 堆的顶部优先级最高。例如大根堆堆顶数字最大，小根堆堆顶数字最小。为什么说是优先级最高，因为堆并不只能根据数字大小来维护堆内元素的顺序，还可以通过别的方式更改这些顺序（例如重载）。某些题就不是按数字的大小为优先级来进行堆的操作的。
3. 当前节点的儿子优先级都比当前节点小，且左儿子小于右儿子。

3、堆的原理（操作）

以下演示的都为小根堆。

1、插入

我们先考虑插入在哪里。为了要满足堆的性质 1，那我们选择加在堆底，即：

此时并不满足性质 3，我们通过向上交换的方式，逐步寻找它应该在的位置。 如图：事实上堆的插入就是把新的元素放到堆底，然后检查它是否符合堆的性质，如果符合就说明排好了，如果不符合，那就和它的父亲交换一下，一直交换交换交换，直到符合堆的性质，那么就插入完成了。

其实插入的过程中，不必考虑性质三的后半段，这会在删除时满足。查询时，也不用考虑，因为堆顶只有一个。

代码：

void modify(int x)
{
    if(x==1||w[x]>w[x/2]) return ;//根节点或满足性质停止交换
    swap(w[x],w[x/2]);
    modify(x/2);//用递归的方式，往上交换
}
void push(int x)
{
    w[++tot]=x;//插入堆底
    modify(tot);
}

2、删除

假设我们要删除堆顶的 1。

我们还是要保持堆的性质 1，我们可以把堆顶与堆底交换，然后删除堆底。但此时就又不满足性质 3 了，那么我们把堆顶向下交换。

堆顶向下交换过程中，在它的两个儿子里面，找一个比较小的，且是小于它的，和它交换一下。直到满足性质，即两个儿子都比它大。

代码：

void repair(int x)
{
    if(x*2>tot)return ;//注意不能超过堆底
    int tar=x*2;
    if(x*2+1<=tot) tar=w[x*2]<w[x*2+1]?x*2:x*2+1;//找小的儿子
    if(w[x]>w[tar])//如果不满足性质，则继续向下交换
    {
        swap(w[x],w[tar]);
        repair(tar);
    }
}
void pop()
{
    swap(w[1],w[tot--]);//交换并删除
    repair(1);
}

3、查询

没什么好讲，直接输出堆顶。

好，到目前为止讲的都没什么用，但是如果你们够牛，有实力学到左偏树的话，那还是有用的（不过笔者不会）。

4、堆的 STL 实现

定义一个优先队列：

#include<queue>//需要的头文件
priority_queue<int> q;//这是一个大根堆q
priority_queue<int,vector<int>,greater<int> >q;//这是一个小根堆q
//注意某些编译器在定义一个小根堆的时候greater<int>和后面的>要隔一个空格，不然会被编译器识别成位运算符号>>

优先队列的操作：

q.top()//取得堆顶元素，并不会弹出
q.pop()//弹出堆顶元素
q.push()//往堆里面插入一个元素
q.empty()//查询堆是否为空，为空则返回1否则返回0
q.size()//查询堆内元素数量

因为 STL 好写，下面堆的应用全部都会采用 STL 的代码实现。

5、关于堆的复杂度

由于是完全二叉树，插入删除复杂度为 O( \log n)，n 为节点数。

6、堆的应用

1、基本操作

这一部分的二叉堆仅仅作为一个工具，主要还是思路。

P1177 将 n 个数从小到大排序后输出。

输入时每次插入维护堆，最后不停输出堆顶，不停删除即可。

代码不给。

P1090 共 n 个数，每次合并两个数，代价为两个数的和，求合并 n-1 次后，最小代价。

考虑贪心，每次合并最小两堆一定最优。

证明：

合并的过程可以看成一棵二叉树，总代价为 \sum_{i=1}^n a_i \times dep_i。a_i 是固定的，那么越大的数 dep_i 越小对于答案的贡献越少，更优。那么优先合并较小数。

那么我们需要维护当前数字中的最小值，可以想到优先队列。每次弹出两个堆顶，并合并再次插入堆中。只剩一个数时，就是答最小贡献。

代码不给。

P2168 k 叉哈夫曼树板子。

首先介绍一下哈夫曼树，哈夫曼树也叫最优二叉树，是一种带权路径（叶子节点权值，即题中的 a_i，乘该节点到根节点路径长度）之和最短的二叉树。如图（这是个二叉哈夫曼树）：

。

最底下的叶子节点就为每个单词的出现次数，树上的 01 就是最后构造出来的哈夫曼编码。

这道题要求的，就是构造出的哈夫曼树的根节点的值，与树的高度。

与合并果子类似，考虑贪心。每次从堆中取出权重最小的 k 的顶点，将其合并再次扔进堆里，直到合并完。

但是这里有一个问题，最后一次合并时可能不足 k 个数，即树的根节点的儿子不足 k 个。那么显然有更优的方式，把任意一个叶子节点换上来就会更优。所以我们要补上 k-1-(n-1)\bmod(k-1) 个节点，把有权重的节点推到里根节点更近的位置。

代码：

2、二叉堆维护对顶堆

这一部分主要可以求一些有关 topk 的题。

对顶堆像是这样，两个堆堆顶相对，上面是小根堆，下面大根堆，从上到下的数，分别是从大到小的（当然也可以反过来）。

对于第 k 小，我们保证大根堆中有 k 个元素，然后输出堆顶即可。

考虑插入一个数如何继续维护这个 topk。

首先要保证对顶堆从上到下的数，分别是从大到小的。如果这个数大于下面这个堆的堆顶，那么往上插入，反之向下插入。

然后要保证大根堆的中有 k 个元素。如果多了，把堆顶向小根堆弹；如果少了，那就从小根堆中拿来数。

但是用对顶堆来维护 topk，如果 k 给定，那好说。如果会变化，每两个 k 之间的取值范围不能太大，因为每一次动态维护的次数都与上一次有关，这会影响到复杂度，甚至如果一次求第一，一次求第 n，那么会被卡到 O(Tn \log n)。

P1168 给定一个数组，对于前奇数项求中位数。

那显然，我们对第 i 个项 (i 为奇数) 求第 \lfloor {i/2}\rfloor+1 小的数。

首先在每个数插入时，先保证大小之间的性质。到了每奇数项，再进行微调，把底下大根堆中把多的或者少的数调掉，每次输出它的堆顶。

代码（略有区别，我这里是每次都先拿出一个值当中位数，也就是两个堆里的数少了 1 个）：

for(int i=2,x;i<=n;i++)
    {
        cin>>x;
        if(x>mid) p.push(x);
        else q.push(x);
        if(i&1)
        {
            while(q.size()!=p.size())
            {
                if(q.size()>p.size())
                {
                    p.push(mid);
                    mid=q.top();
                    q.pop();
                }
                else 
                {
                    q.push(mid);
                    mid=p.top();
                    p.pop();
                }
            }
            cout<<mid<<"\n";
        }
    }

P7072 根据题意每次维护第 \max(1,p\times w) 大，对顶堆板子。

注意维护的是第 k 大，对顶堆要反着来。在小根堆中，存 k 个数。

代码：

void push(int s)
{
    if(s>=ma.top()) mi.push(s);//插入
    else ma.push(s);

    if(mi.size()>now)
    {
        ma.push(mi.top());
        mi.pop();
    }
    if(mi.size()<now)
    {
        mi.push(ma.top());
        ma.pop();
    }//进行微调，这道题中最多也只需要微调一次
}

P1801 不讲了，反正也是板子题。

3、用二叉堆维护一些合并问题

P1631 有两个长度为 n 的单调不降序列 A,B，在 A,B 中各取一个数相加可以得到 n^2 个和，求这 n^2 个和中最小的 n 个。

首先排序。

我们考虑哪些数有机会参与贡献。假设我们当前数 k 是由 a_i 与 b_j 构成，那如果 k 是 n 个最小的数的其中一个，那么，a_i 与 b_{j+1} 是有可能的，即当前数 k 往后枚举的第一个。如果现在这个都不行，那也没必要再向后考虑。也就是每次取出堆中的最小值。若这个最小值来自于第 k 个队列（这里的队列是指 a_k 与 b 数组的搭配），那么，就将第 k 个队列的下一个元素放入堆中。

代码：

    for(int i=1;i<=n;i++) q.push(make_pair(a[i]+b[1],1));//先插入每个队列的第一个，这些还都有可能
    for(int i=1;i<=n;i++)
    {
        pair<int,int> p=q.top();
        q.pop();
        cout<<p.first<<" ";//取出队头，并向后拓展有可能的位置
        q.push(make_pair(p.first-b[p.second]+b[p.second+1],p.second+1));
    }

P2085

我们先考虑暴力是怎么做的，对于每个函数算出其变量 x=1\sim m 时的函数值，全部存到一个数组中，排序后输出前 m 个。

这时候，很多后面的数实际上是参与不到贡献中的，也就是说这些数根本没必要算出来。

考虑优化。首先将 x=1 时的 n 个函数值加入优先队列内。

每次，如果一个数是可能出现在输出中的，那么它的前一个，即变量为 x-1 一定输出过（由于函数递增）。如果他的上一个也没有输出，当前这个只会更大，就没必要加进优先队列中。我们只需要输出一个，将 x+1 向后拓展即可。

主要代码：

for(int i=1;i<=n;i++)
    {
        cin>>a[i]>>b[i]>>c[i];
        l[i]=1;
        pair<int,int> p;
        p.first=f(a[i],b[i],c[i],l[i]);
        p.second=i;
        q.push(p);//首先预处理出哪些是有可能的
    }
    for(int i=1;i<=m;i++)
    {
        pair<int,int> p=q.top();
        q.pop();
        cout<<p.first<<" ";
        int t=p.second;
        l[t]++;
        p.first=f(a[t],b[t],c[t],l[t]);//向后拓展
        q.push(p);
    }

4、二叉堆杂题

P2827 蚯蚓

这道题参考合并果子，每次从蚯蚓堆中找到最大的一条，把他切掉，再放回去。但是放回去时，其它的蚯蚓长度都要增加 q，如何解决？由于大小关系是相互的，那么相当于当前切出来的这两条蚯蚓减少 q。但是在计算真正长度时，还要把这些偏移量给加回去，还要加回去若干个 q。

代码：

for(register int i=1;i<=m;i++)
    {
        int now=qu.top()+dick;//dick为偏移量，这里算出真实长度
        qu.pop();
        int q1,q2;
        q1=int(1.0*u/v*now);
        q2=now-q1;//算出两条的长度
        dick+=q;//偏移量累加
        q1-=dick,q2-=dick;//再把这两条再偏移回去
        qu.push(q1),qu.push(q2);//重新放入堆里
        if(i%t==0) write(now),putchar(' ');
    }

好，只有 90 分。

满分思路与二叉堆无关，不讲了，自己看题解。反正就是每次切出来的蚯蚓长度也具有单调性，不需要二叉堆维护。

P4053 考虑贪心。

第一个很显然的贪心策略，我们要把它的截止时间从小到大排序。对于那些不紧急的任务，可以往后再做。

排序后，我们遍历所有建筑，如果它在当前时间能被修好，那就修；如果不能，那么此时必然要废除掉一个建筑。我们考虑废除之前修的哪一座最优，显然，肯定废除修理时间最长的建筑。

在这里每次找之前时间最长的建筑，就可以用二叉堆来维护。

代码：

for(int i=1;i<=n;i++)
    {
        if(time+a[i].x<=a[i].y)//如果可以修理，那就修理，并加入已修理的堆里。为后面反悔的操作考虑。
        {
            daan++;
            time+=a[i].x;
            q.push(a[i].x);
        }
        else 
        {
            if(a[i].x<q.top())//需要废除
            {
                time=time-q.top()+a[i].x;
                q.pop();
                q.push(a[i].x);//废除最大的（即大根堆的堆顶）
            }
        }
    }

之前绍兴市赛小学组 T4 也是反悔贪心。

P2278 大模拟

我们可以用堆来维护各进程的优先级关系。

每次先按优先级关系一直往下做，直到再做下去就比当前输入的进程时间要晚了。

剩下考虑两种情况。 1、当前输入的进程优先级是最高的，那么我们就先把正在做的这个进程做一半，重新放回堆里，再接着像之前那样考虑，按优先级关系往下做。

2、优先级比较低，那我们直接把这个放入堆中，也像之前一样考虑即可。

这样过于麻烦，所以我们需要一种通用解法：

可以发现，第一种情况的处理方法对于第二种情况同样适用，把当前进程执行一半，我们算出他能够执行的时间，更新这个进程并且重新放回堆中。

while(scanf("%d%d%d%d",&x.id,&x.st,&x.ti,&x.pr)!=EOF)
    {
        while(!q.empty()&&now+q.top().ti<=x.st)//先是普通情况。
        {
            info y=q.top();
            q.pop();
            cout<<y.id<<" "<<now+y.ti<<"\n";
            now+=y.ti;
        }
        if(!q.empty())
        {
            info z=q.top();
            q.pop();
            z.ti=z.ti+now-x.st;
            q.push(z);//考虑为当前进程执行一半
        }
        q.push(x);//把当前输入进程也放入堆中。
        now=x.st;//在这里，我们已经把在输入当前进程的时间前的所有情况都统计完了
    }

7、重载运算符

对于一些需要按，比较复杂的规则，在优先队列内排序的题，我们就需要重载运算符

具体写法：

struct info//写在结构体内
{
    int x,y; 
    bool operator <(const info &a)const{//注意这里必须要是<
        return a.x<x;//注意这里"a."不能与后面的交换，其他与自定义排序的写法一样。
    }
};
priority_queue<info> q; //比如这里就是按结构体的x从小到大排序

struct info
{
    int x,y; 
    bool operator <(const info &a)const{
        return a.x<x||(a.x==x&&a.y<y);
    }
};
priority_queue<info> q; //这里就是先按x从小到大排序，再按y从小到大排序

完结撒花。