（二叉）堆算法总结

堆是一种数据结构，经常被用来维护一组数据的最值。

可以用 C++ 自带的 priority_queue 维护，也可以自己手写二叉堆。

手写二叉堆

二叉堆要维护一个区间的最值，要支持两个操作：上浮和下沉。

上浮能使这个数据结构里的最小值 “浮” 到堆顶，下沉能使这个数据结构里的较大值 “沉” 到堆中或者堆底。

因为他是二叉堆，所以非常好维护，但是他的一个插入（上浮）或一个删除（下沉）操作就要用的时间复杂度。

这里的堆的编号与线段树相似，左儿子是，右儿子是。但是这里特殊的一点就是不能有空结点。

插入/上浮

首先把一个数据插入到堆的的后一个节点，这个点可能与编号为的点在一层，也可能这个点在它的下一层。之后。以小根堆为例，为了维护堆顶的元素必须是整个堆的最小值，插入后，若他的父亲节点数值比这个点大，那么就交换该点和父亲节点，然后指针指向父亲节点。如此往复，直到他在堆顶或是它的值比它父亲的大。

削除堆顶/下沉

首先把堆顶删了，然后再把编号为的点拿出来，放到堆顶。这时发现堆顶的数可能不是最小的，所以要下沉，把下面比这个数小的移上来。操作与上浮类似，把这个点与他的儿子比较，找到他数值最小的儿子，交换它与它的数值最小的儿子节点，指针指向数值最小的儿子节点。如此往复，直到他在堆底或是它的值比它儿子的小。

模板代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+7;
int heap[N], len;
void insert(int x){
    heap[++len] = x;
    for(int i=len;i!=1;i/=2){
        if(heap[i] < heap[i/2]) swap(heap[i], heap[i/2]);
    }
}
void del(){
    heap[1] = heap[len--];
    int i = 1;
    while(i*2<=len){
        int son = 2*i;
        if(son+1 <= len && heap[son+1] < heap[son]){
            son = 2*i+1;
        }
        if(heap[i] > heap[son]) swap(heap[i], heap[son]), i = son;
        else break;
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int q;
    cin>>q;
    int op, x;
    while(q--){
        cin>>op;
        if(op==1) cin>>x, insert(x);
        else if(op==2) cout<<heap[1]<<'\n';
        else if(op==3) del();
    }
    return 0;
}

例题

P1090 合并果子

这道题是一个经典贪心，维护一个小根堆，把他最小的两个数取出来，然后合并这两个点（ans += top1 + top2），再把这个相加的结果放进堆里。因为这个堆是实时更新的，所以可以保证取出来的两个值绝对是堆中最小的两个值。模拟即可。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
//priority_queue<int, vector<int>, greater<int> > q;
int h[N], len;
void insert(int x){
    h[++len] = x;
    int i = len;
    while(i/2 >= 1){
        if(h[i] < h[i/2]) swap(h[i], h[i/2]), i/=2;
        else break;
    }
}

void del(){
    h[1] = h[len--];
    int i = 1;
    while(i*2<=len){
        int son = i*2;
        if(son+1<=len&&h[son] > h[son+1])
            son ++;
        if(h[i] > h[son]) swap(h[i], h[son]), i = son;
        else break;
    }
}

int n;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin>>n;
    int x, y;
    for(int i=1;i<=n;i++){
        cin>>x;
        insert(x);
    }
    long long ans = 0;
    for(int i=1;i<n;i++){
        x = h[1];
        del();
        y = h[1];
        del();
        ans += (x+y);
        insert(x+y);
    }
    cout<<ans;
    return 0;
}

P1168 中位数

首先解决第一项。1个数的数列他的中位数就是它唯一的元素。我们假设这个数为。然后再解决第项。我们钦定第一项为，设置一个大根堆和一个小根堆。将这两项中大于等于的数插入小根堆，小于的数插入大根堆。容易发现这两个堆的元素个数很有可能不等，这时就不是中位数了。

再考虑把元素多的堆的元素向转移，再向元素少的堆转移，就能使两个堆的元素个数一样多，就是中位数了。后面的操作同理。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
priority_queue<int, vector<int>, greater<int> > sq;
priority_queue<int, vector<int>, less<int> > bq;

int n;
int a[N];

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    int mid = a[1];
    cout<<mid<<'\n';
    for(int i=3;i<=n;i+=2){
        if(a[i-1] >= mid)  sq.push(a[i-1]);
        else bq.push(a[i-1]);
        if(a[i] >= mid) sq.push(a[i]);
        else bq.push(a[i]);
        while(sq.size() < bq.size()){
            sq.push(mid);
            mid = bq.top();
            bq.pop();
        }
        while(sq.size() > bq.size()){
            bq.push(mid);
            mid = sq.top();
            sq.pop();
        }
        cout<<mid<<'\n';
    }
    return 0;
}

P2085 最小函数值

~~啊→啊→啊↓咦↗~啊↓咦↗~啊→啊↑啊↓啊～嗯↓哎↓哎↓哎↑哦↑哎→嗯↓~哦→哎↑爱爱爱爱爱~~

因为这道题特殊的范围： ${x\in\mathbb{N}} $，又因为$ A, B, C \ge 1 $，可以发现这个函数的最小值点的$ x $值是$ -\frac{B}{2A} \lt 0 $，所以当$ {x\in\mathbb{N}} $时，$ y $一定随$ x $的增大而增大。所以这个函数的最小值一定从$ x = 1 $开始，$ 1 $被选了然后选$ 2, 3$…

再看这道题有很多个函数，容易发现这些函数都是时最小。于是我们定义一个结构体，里面有函数的值和这个对应的值。再以为关键字建一个小根堆，把所有的情况全部 push 进去。取最小值之后，为了不遗漏情况，还要把这个最小值对应函数的值的情况也给 push 进去，然后简单维护即可。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e4+5;
struct node{
    int val, idx, num;
};
bool operator < (const node &a, const node &b){
    return a.val < b.val;
}
bool operator > (const node &a, const node &b){
    return a.val > b.val;
}
priority_queue<node, vector<node>, greater<node> > q;
int a[N], b[N], c[N];
int getf(int idx, int x){
    return a[idx]*x*x + b[idx]*x + c[idx];
}
int n, m;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i]>>b[i]>>c[i];
        q.push({getf(i, 1), i, 1});
    }
    for(int i=1;i<=m;i++){
        cout<<q.top().val<<' ';
        int qti = q.top().idx, qtn = q.top().num;
        q.pop();
        q.push({getf(qti, qtn+1), qti, qtn+1});
    }
    return 0;
}

P2827 蚯蚓

虽然这道题似乎和堆完全没有关系……但是85分是可以用堆硬搞出来的。

85pts

模拟，建立一个大根堆，最开始把所有蚯蚓的长度全部都 push 到一个大根堆里。每次要修改的时候，把长度最长的一直蚯蚓取出来，然后把他分成两段，再 push 回大根堆里。但是把其他元素全部加是不现实的，所以我们可以定义一个偏移量，每次取出最大值的时候要加上这个，改了之后再减去，再把偏移量加上即可。但是注意到，这个的时间复杂度是，所以会TLE。

100pts

和堆没啥关系。

但和队列有关系。

我们可以考虑沿用85pts的思路，取出里面的最大值然后切除，再把它塞到最小值。

（但是如何维护？最开始的那个元素还好，后面切除了之后又怎么让切除的两段走到对的位置上去？）

我们知道最开始那n个元素排序了之后是单调不增的，那么把这些元素分别切除（先不增加）的那些长度会不会也是单调不增的呢？

容易发现，那另外一段呢？

考虑证明：已知，如何证明？

首先根据条件可得：

$x_1 - x_2 \ge p(x_1 - x_2)$

移项：

$x_1 - x_2 + px_2 \ge px_1$

然后都向下取整：

$\lfloor x_1 - x_2 + px_2 \rfloor \ge \lfloor px_1\rfloor$

之后把和提取出来，因为是整数，所以结果不变：

$x_1 - x_2 + \lfloor px_2\rfloor \ge \lfloor px_1\rfloor$

然后移项即得证。

（：已知，如何证？首先把分为整数部分和小数部分。若整数部分相同，那么忽略小数部分，可得。若整数部分不同，那么。）

我们维护3个队列，第一个队列从大到小存放开始的那些长度，第二个队列从大到小存放，第三个队列从大到小存放。因为之前证明了这个单调性（第一个单调，那第二个和第三个也单调），所以就可以在3个队列里选个最大值，把最大值 pop了，再把最大值加上分为两段，然后把切出来的两段处理后分别 push进第二个和第三个队列。这样就舍去了这个，复杂度线性。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+5;
queue<ll> stt, cutlft, cutrgt;
int n, m, q, t;
ll u, v;
ll a[N];
ll delta;
bool cmp(ll x, ll y){
    return x > y;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin>>n>>m>>q>>u>>v>>t;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    sort(a+1, a+1+n, cmp);
    for(int i=1;i<=n;i++){
        stt.push(a[i]);
    }
    //每次选一个最长的蚯蚓，把它切了，左半部分放cutlft，右半部分放cutrgt
    ll maxn, maxidx;
    delta = 0;
    for(int i=1;i<=m;i++){
        maxn = -0x3f3f3f3f3f3f3f3f, maxidx = 0;
        if(!stt.empty() && maxn < stt.front()) maxn = stt.front(), maxidx = 1;
        if(!cutlft.empty() && maxn < cutlft.front()) maxn = cutlft.front(), maxidx = 2;
        if(!cutrgt.empty() && maxn < cutrgt.front()) maxn = cutrgt.front(), maxidx = 3;
        if(maxidx == 1) stt.pop();
        if(maxidx == 2) cutlft.pop();
        if(maxidx == 3) cutrgt.pop();
        maxn += delta;
        if(i%t==0){
            cout<<maxn<<' ';
        }
        ll worm1 = maxn * u / v;
        ll worm2 = maxn - worm1;
        worm1 -= (delta + q), worm2 -= (delta+q);
        cutlft.push(worm1), cutrgt.push(worm2);
        delta += q;
    }

    //Output
    cout<<'\n';
    for(int i=1;i<=m+n;i++){
        maxn = -0x3f3f3f3f3f3f3f3f, maxidx = 0;
        if(!stt.empty() && maxn < stt.front()) maxn = stt.front(), maxidx = 1;
        if(!cutlft.empty() && maxn < cutlft.front()) maxn = cutlft.front(), maxidx = 2;
        if(!cutrgt.empty() && maxn < cutrgt.front()) maxn = cutrgt.front(), maxidx = 3;
        if(maxidx == 1) stt.pop();
        if(maxidx == 2) cutlft.pop();
        if(maxidx == 3) cutrgt.pop();
        maxn += delta;
        if(i%t==0){
            cout<<maxn<<' ';
        }
    }
    return 0;
}

P3045 Cow Coupons G

反悔贪心 + 堆。

首先我们先选取值最小的头奶牛，这是显然的，因为这样可以使前个奶牛总花费最小。然后后面的怎么贪心？如果后面的选到了一个更好的，我们可以反悔。把之前选了的一头奶牛不用购买，用原价购买，然后这头牛再用购买，只能这头购买了比之前的某一头更优才能选这头。比之前更优的条件是什么？

假设现在一共花费了，之前选了的有一头的编号为，当前看上的这一头编号为。放弃而选的条件只有：

$tot - C_j + P_j + C_i < tot + P_i$

我们发现可以删除，再移项可得：

$P_j - C_j < P_i - C_i$

设第头奶牛的优惠力度（）为，那么要满足：

$\Delta_j < \Delta_i$

那么我们可以分别维护以为关键字的小根堆，把从小到大选。若选到买过的那就跳过。如果扫到当前的和的大于已选的堆顶，那么就用优惠券。放弃以前的优惠，选择现在的优惠。每选一个就让当前剩下的钱减去当前价格，若是反悔那就反悔之前选的再减去现在的优惠价格。当时，不符合条件，跳出循环。为了方便让前个元素全用优惠券，就让堆里面 push 个。

#include<bits/stdc++.h>
using namespace std;
const int N = 5e4+5;
typedef long long ll;
ll orip[N], oric[N];
struct node{
    ll val, idx;
};
bool operator < (const node &x, const node &y){
    return x.val < y.val;
}
bool operator > (const node &x, const node &y){
    return x.val > y.val;
}
priority_queue<node, vector<node>, greater<node> > p, c;
priority_queue<ll, vector<ll>, greater<ll> > delta;

int k, n;
ll m;
bool vis[N];//这个玩意有没有被买过
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin>>n>>k>>m;
    for(int i=1;i<=n;i++){
        cin>>orip[i]>>oric[i];
        p.push({orip[i], i});
        c.push({oric[i], i});
    }
    for(int i=1;i<=k;i++){
        delta.push(0);
    }
    int ans = 0;
    while(!p.empty()){
        int pfr = p.top().idx;
        int cfr = c.top().idx;
        if(vis[pfr]){
            p.pop();
            continue;
        }
        if(vis[cfr]){
            c.pop();
            continue;
        }
        if(delta.top() > orip[pfr] - oric[cfr]){
            m -= orip[pfr];
            vis[pfr] = 1;
            p.pop();
        }else{
            m -= delta.top() + oric[cfr];
            vis[cfr] = 1;
            c.pop();
            delta.pop();
            delta.push(orip[cfr] - oric[cfr]);
        }
        if(m>=0) ans++;
        else break;
    }
    cout<<ans;
    return 0;
}