洛谷-P3378 题解

发表于2023-05-05更新于2023-05-05

题目传送门

一道小根堆模板题……

在做这道题之前，我们先介绍一下小根堆是什么。

我们定义小根堆是一种对于任何一个父结点的权值总是小于或等于子节点权值的完全二叉树。因此，不难看出，一个小根堆的堆顶（这棵树的根节点）应该是这个堆（树）中权值最小的结点。

简单介绍完了小根堆，我们再介绍下如何存储。

存储

我们考虑用一个数组进行存储，用一个变量来记录堆里的元素个数。

1
2
int heap[1000005]; // 用数组存储
int cnt; // 记录堆中的元素个数，也是下一个元素插入进来的位置

学会了如何存储小根堆，接下来我们要实现几个操作：

  • 插入一个数

  • 查询堆顶

  • 删除堆顶

插入一个数

我们需要在最后一个位置插入，然后从下往上进行维护。如果发现父结点的权值大于子结点的权值，则将子结点与父结点进行交换，然后继续往上进行搜索。

1
2
3
4
5
6
7
8
9
10
11
void xds(int cur) { 
    int fa = (cur - 1) / 2; // 父亲结点的位置
    if (heap[fa] > heap[cur]) { // 如果不合法
        swap(heap[fa], heap[cur]); // 进行交换
        xds(fa); // 继续往上维护
    }
}
void insert(int x) {
    heap[cnt] = x; // 插入
    xds(cnt++); // 维护
}

查询堆顶

之前说过，堆顶应该是整个堆中最小的元素，而我们插入维护是从下往上进行维护（对于整个数组，我们可以说是从后往前进行维护）的，因此堆顶为 heap[0]。

删除堆顶

我们可以将堆顶与最后一个元素进行互换，然后将长度减 11，就相当于删掉了这个元素。之后我们从上往下维护一遍，我们分成没有子结点，有一个子结点，有两个子结点这 33 种情况进行维护，原理与插入差不多。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void sdx(int cur) {
    if (2 * cur + 1 >= cnt) return ; // 没有子结点
    if (2 * cur + 2 >= cnt) { // 有一个子结点
        if (heap[2 * cur + 1] < heap[cur]) swap(heap[2 * cur + 1], heap[cur]);
        return ;
    }
    int l = 2 * cur + 1, r = l + 1;
    if (heap[l] > heap[r]) swap(l, r); // 确定哪个子结点跟这个结点交换
    if (heap[l] < heap[cur]) { // 不合法
        swap(heap[l], heap[cur]); // 交换
        sdx(l); // 继续往下维护
    }
}
void del() {
    swap(heap[0], heap[--cnt]); // 删掉堆顶
    sdx(0); // 从上往下进行维护
}

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <bits/stdc++.h>
#define ll long long
#define INF 1e9
using namespace std;
int n;
int heap[1000005]; // 用数组存储
int cnt; // 记录堆中的元素个数，也是下一个元素插入进来的位置
void xds(int cur) { 
    int fa = (cur - 1) / 2; // 父亲结点的位置
    if (heap[fa] > heap[cur]) { // 如果不合法
        swap(heap[fa], heap[cur]); // 进行交换
        xds(fa); // 继续往上维护
    }
}
void insert(int x) {
    heap[cnt] = x; // 插入
    xds(cnt++); // 维护
}
void sdx(int cur) {
    if (2 * cur + 1 >= cnt) return ; // 没有子结点
    if (2 * cur + 2 >= cnt) { // 有一个子结点
        if (heap[2 * cur + 1] < heap[cur]) swap(heap[2 * cur + 1], heap[cur]);
        return ;
    }
    int l = 2 * cur + 1, r = l + 1;
    if (heap[l] > heap[r]) swap(l, r); // 确定哪个子结点跟这个结点交换
    if (heap[l] < heap[cur]) { // 不合法
        swap(heap[l], heap[cur]); // 交换
        sdx(l); // 继续往下维护
    }
}
void del() {
    swap(heap[0], heap[--cnt]); // 删掉堆顶
    sdx(0); // 从上往下进行维护
}
signed main() {
    ios :: sync_with_stdio(0);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int op;
        cin >> op;
        if (op == 1) {
            int x;
            cin >> x;
            insert(x);
        }
        else if (op == 2) cout << heap[0] << "\n";
        else del();
    }
    return 0;
}