堆 二叉搜索树

发表于 更新于 分类于 ， 阅读次数： 作者 Pomelorin

二叉堆

介绍

二叉堆主要支持的操作有：插入一个数 \(O(\log n)\)、查询最小值 \(O(1)\)、删除最小值 \(O(\log n)\)。

二叉堆是一棵完全二叉树，其每个节点都有一个值，且每个节点的值都大于等于/小于等于其父亲的值。每个节点的值都大于等于其父亲值的堆叫做小根堆（即根最小），否则叫做大根堆。STL 中的 priority_queue 其实就是一个大根堆。

接下来以小根堆为例。由堆性质，树根（堆顶）存的是最小值。

二叉堆可以用一个数组来存储，下标表示编号。对于编号为 p 的节点，p*2 即为左儿子，p*2+1 即为右儿子，p/2 即为父节点。同时，用 size 记录当前二叉堆中节点的个数。

基础操作

向上调整：如果这个结点的权值小于它父亲的权值，就交换，重复此过程直到不满足或者到根。

向下调整：在该结点的儿子中，找一个权值最小的，如果这个权值小于该结点，与该结点交换，重复此过程直到不满足或者到底层。

二叉堆可视化演示 -7,-26,-25,-19,-17,-90,-3,-36,-87

两个操作复杂度均为 \(O(\log n)\)。

基本操作

插入：向二叉堆中插入一个元素。方法为在数组末尾插入，之后向上调整。可以证明，插入之后向上调整后，没有其他结点会不满足堆性质。

删除：删除二叉堆其中一个元素。方法为将此结点和最后一个结点交换，直接删掉，之后向下调整。可以证明，删除并向下调整后，没有其他结点不满足堆性质。

查询：查询二叉堆中最小值。堆顶即为最小值。

另外，还支持任意节点的删除、修改。

代码参考

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<ll,ll>
#define lson (root*2)
#define rson (root*2+1)
#define dad (root/2)
const ll N = 1e6 + 10;

struct Heap {
    ll h[N] = {}, n = 0;

    ll up(ll root) {
        while (root > 1 && h[root] < h[dad]) {
            swap(h[root], h[dad]);
            root = dad;
        }
        return root;
    }

    ll down(ll root) {
        while (lson <= n) {
            ll temp = lson;
            if (rson <= n && h[rson] < h[lson])
                temp = rson;
            if (h[temp] >= h[root])
                break;
            swap(h[root], h[temp]);
            root = temp;
        }
        return root;
    }

    void build(ll siz, ll a[]) {
        n = siz;
        for (ll i = 1; i <= n; i++)
            h[i] = a[i];
        for (ll i = n; i >= 1; i--)
            down(i);
    }

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

    ll push(ll val) {
        h[++n] = val;
        return up(n);
    }

    void pop(ll key = 1) {
        swap(h[key], h[n]);
        n--;
        down(1);
    }
}q;

//priority_queue<ll, deque<ll>, greater<ll> > q;

void solve() {
    ll n;
    cin >> n;
    for (ll i = 1; i <= n; i++) {
        ll op, tmp;
        cin >> op;
        if (op == 1) {
            cin >> tmp;
            q.push(tmp);
        } else if (op == 2) {
            cout << q.top() << endl;
        } else {
            q.pop();
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    ll T;
    T = 1;
    while (T--) {
        solve();
    }
    return 0;
}

堆的 STL 实现

一般来说，我们在写算法题时常用优先队列替代手写二叉堆。

1
2
3
4
5
6
7
priority_queue<ll, deque<ll>, greater<ll> > q; //小根堆
priority_queue<ll> q;  //大根堆

q.push(x); //插入
q.top(); //查询堆顶元素
q.pop(); //删除堆顶元素
q.empty(); //堆是否为空

例题

  • P3378 【模板】堆 https://www.luogu.com.cn/problem/P3378（模板）

  • P1168 中位数 https://www.luogu.com.cn/problem/P1168 （对顶堆）

    给定一个长度为 \(N\) 的非负整数序列 \(A\)，对于前奇数项求中位数。

  • CSP-S 2021 廊桥分配 https://www.luogu.com.cn/problem/P7913 （较有挑战性）

    现有 \(n\) 个廊桥（停飞机的地方），\(m_1\) 架国内航班，\(m_2\) 架国外航班。给定航班时间表，求出应当如何分配 \(n\) 个廊桥，使得可停靠廊桥的飞机数量最多。飞机遵从“先到先得”原则，若飞机到达时无空闲廊桥，则此飞机无法停靠。

二叉搜索树

定义

二叉搜索树可支持的操作一般有：插入、删除、查询 \(x\) 的排名、查询排名为 \(k\) 的数、查询前驱与后继。

二叉搜索树是一种二叉树的树形数据结构，其定义如下：

  1. 空树是二叉搜索树。
  2. 若二叉搜索树的左子树不为空，则其左子树上所有点的权值均小于其根节点的值。
  3. 若二叉搜索树的右子树不为空，则其右子树上所有点的权值均大于其根节点的值。
  4. 二叉搜索树的左右子树均为二叉搜索树。

set 与 map 的内部数据结构即为平衡树。使用搜索树的目的之一是缩短插入、删除、修改和查找节点的时间。在最坏情况下，搜索树有可能退化为链。想象一棵每个结点只有右孩子的二叉搜索树，那么它的性质就和链一样，所有操作（增删改查）的时间复杂度是 \(O(n)\)。

可以发现操作的复杂度与树的高度 \(h\) 有关。由此引出了平衡树，通过一定操作维持树的高度（平衡性）来降低操作的复杂度，使得所有操作时间复杂度达到 \(O(\log n)\)。感兴趣的同学可以进一步学习 Treap、Splay 等平衡树。

操作

二叉搜索树可视化演示

查找最小/最大值

由二叉搜索树的性质可得，二叉搜索树上的最小值为二叉搜索树左链的顶点，最大值为二叉搜索树右链的顶点。

搜索元素

在以 root 为根节点的二叉搜索树中搜索一个值为 value 的节点。

分类讨论如下：

  • 若 root 为空，返回 false。
  • 若 root 的权值等于 value，返回 true。
  • 若 root 的权值大于 value，在 root 的左子树中继续搜索。
  • 若 root 的权值小于 value，在 root 的右子树中继续搜索。

插入，删除，修改都需要先在二叉搜索树中进行搜索。

插入一个元素

在以 root 为根节点的二叉搜索树中插入一个值为 value 的节点。

分类讨论如下：

  • 若 root 为空，直接返回一个值为 value 的新节点。
  • 若 root 的权值等于 value，该节点 count 加一。
  • 若 root 的权值大于 value，在 root 的左子树中插入权值为 value 的节点。
  • 若 root 的权值小于 value，在 root 的右子树中插入权值为 value 的节点。

删除一个元素

在以 root 为根节点的二叉搜索树中删除一个值为 value 的节点。

先在二叉搜索树中搜索权值为 value 的节点，分类讨论如下：

  • 若该节点的 count 大于 11，只需要减少 count。
  • 若该节点的 count 为 11：
    • 若 root 为叶子节点，直接删除该节点即可。
    • 若 root 为链节点，即只有一个儿子的节点，返回这个儿子。
    • 若 root 有两个非空子节点，一般是用它左子树的最大值（左子树最右的节点）或右子树的最小值（右子树最左的节点）代替它，然后将它删除。

求元素的排名

排名定义为将数组元素升序排序后第一个相同元素之前的数的个数加一。

查找一个元素的排名，首先从根节点跳到这个元素，若向右跳，答案加上左儿子节点个数加当前节点重复的数个数，最后答案加上终点的左儿子子树大小加一。

查找排名为 k 的元素

在一棵子树中，根节点的排名取决于其左子树的大小。

  • 若其左子树的大小大于等于 \(k\)，则该元素在左子树中；
  • 若其左子树的大小在区间 \([k-count,k−1]\)（count 为当前结点的值的出现次数）中，则该元素为子树的根节点；
  • 若其左子树的大小小于 \(k-count\)，则该元素在右子树中。