二叉堆与并查集

First Post: 2023-01-12
Last Update: 2023-01-12

如果理解递归有困难的，可以先看之前的章节

二叉堆

又称优先队列，此文中我们简称堆(heap)

堆是可以返回该集合的最值的数据结构，但是排序算法也是可以查询最值，那么堆有什么独特的优势吗？我们可以先看看堆的成员方法的时间复杂度：push&pop时间复杂度皆为O(㏒₂n)，查询最值O(1)。可以看出，堆可以在线的回答当前的最值，即动态维护最值；而排序算法多用于事先确定的数集。

在平时的算法比赛或者练习中我们都是使用STL中提供的priority_queue泛型，但是理解其代码实现也是大有裨益之事。

priority_queue的C++实现

该实现支持push，pop，top操作

#include <iostream>

#define lc (u << 1)
#define rc (u << 1 | 1)
#define pa (u >> 1)

using namespace std;

const int N = 1e5 + 10;

int h[N], cnt;

void down(int u)
{
    int t = u;
    if ((lc) <= cnt && h[lc] < h[t]) t = lc;
    if ((rc) <= cnt && h[rc] < h[t]) t = rc;
    
    if (u != t)
    {
        swap(h[t], h[u]);
        down(t);
    }
}

void up(int u)
{
    if (pa && h[pa] > h[u])
    {
        swap(h[pa], h[u]);
        up(pa);
    }
}

int top()
{
    return h[1];
}

void push(int x)
{
	h[++cnt] = x;
    up(cnt);
}

void pop()
{
    swap(h[1], h[cnt]);
    cnt -- ;
    down(1);
}

堆掌握这些就足够了，以后在学习过程中不会手写堆的

并查集

以后LCA问题中tarjan算法会用到哦

并查集是支持合并集合，询问俩个元素是否在一个集合当中的数据结构，具体内容我们课上讲。

路径压缩优化示意图：

例题

A-程序自动分析

在实现程序自动分析的过程中，常常需要判定一些约束条件是否能被同时满足。
考虑一个约束满足问题的简化版本：假设 𝑥1, 𝑥2, 𝑥3, ⋯ 代表程序中出现的变量，给定 𝑛 个形如 𝑥𝑖 = 𝑥𝑗 或 𝑥𝑖 ≠ 𝑥𝑗 的变量相等/不等的约束条件，请判定是否可以分别为每一个变量赋予恰当的值，使得上述所有约束条件同时被满足。例如，一个问题中的约束条件为： 𝑥1 = 𝑥2, 𝑥2 = 𝑥3, 𝑥3 = 𝑥4, 𝑥1 ≠ 𝑥4 ，这些约束条件显然是不可能同时被满足的，因此这个问题应判定为不可被满足。
现在给出一些约束满足问题，请分别对它们进行判定。

输入描述:

第1行包含1个正整数t，表示需要判定的问题个数。注意这些问题之间是相互独立的。

对于每个问题，包含若干行：
第1行包含1个正整数n，表示该问题中需要被满足的约束条件个数。
接下来n行，每行包括3个整数i,j,e，描述1个相等/不等的约束条件，相邻整数之间用单个空格隔开。若e=1，则该约束条件为xi=xj；若e=0，则该约束条件为xi≠xj。

输出描述:

包括t行。

第k行输出一个字符串“YES”或者“NO”（不包含引号，字母全部大写），“YES”表示输入中的第k个问题判定为可以被满足，“NO”表示不可被满足。

输入

输出

NO
YES

说明

在第一个问题中，约束条件为：x1=x2,x1≠x2。这两个约束条件互相矛盾，因此不可被同时满足。

在第二个问题中，约束条件为：x1=x2,x2=x1。这两个约束条件是等价的，可以被同时满足。

备注:

1≤n≤100000

1≤i,j≤1000000000

参考代码

#include <iostream>
#include <unordered_map>
#include <vector>

using namespace std;
using PII = pair<int,int>;

const int N = 2e5 + 10;
int T, n, cnt;
int fa[N];
vector<PII> v[2];
unordered_map<int,int> lsh;

void init(){
    for(int i = 1; i < N; i ++ ){
        fa[i] = i;
    }
    v[0].clear(), v[1].clear();
    cnt = 0;
    lsh.clear();
}

int find(int x){
    if(x == fa[x]) return x;
    return fa[x] = find(fa[x]);
}

void push(int a, int b){
    int pa = find(a), pb = find(b);
    if(pa != pb){
        fa[pa] = pb;
    }
}

signed main(){

    cin >> T;
    string ans;
    while(T -- ){
        cin >> n;
        init();
        ans = "YES\n";
        for(int i = 1; i <= n; i ++ ){
            int a, b, c;
            cin >> a >> b >> c;
            if(c) v[1].push_back({a, b});
            else v[0].push_back({a, b});
            if(lsh[a] == 0) lsh[a] = ++ cnt;
            if(lsh[b] == 0) lsh[b] = ++ cnt;
        }

        for(auto k : v[1]){
            push(lsh[k.first], lsh[k.second]);
        }
        for(auto k : v[0]){
            if(find(lsh[k.first]) == find(lsh[k.second])){
                ans = "NO\n";
                break;
            }
        }

        cout << ans;
    }
}

实战

Supermarket

A-Supermarket

参考代码

#include <iostream>
#include <queue>
#include <algorithm>

#define T first
#define V second

using namespace std;

using PII = pair<int,int>;

const int N = 1e4 + 10;

priority_queue<int, vector<int>, greater<int> > heap;
PII q[N];

signed main()
{
    int n;
    while(cin >> n){
        
    for(int i = 0; i < n; i ++ )cin >> q[i].V >> q[i].T;

    sort(q, q+n);

    heap.push(q[0].V);
    for(int i = 1; i < n; i ++ ){
        if(q[i].T == heap.size() && q[i].V > heap.top()) heap.pop(), heap.push(q[i].V);
        else if(q[i].T > heap.size()) heap.push(q[i].V);
    }

    long long ans = 0;

    while(heap.size())ans += heap.top(), heap.pop();

    cout << ans << endl;
    
    }
}