基础数据结构——1.4二叉树和堆（二）

1.4.2 二叉堆

洛谷 P3378 【模板】堆

时间限制：1.00s　　内存限制：512.00MB

给定一个数列，初始为空，请支持下面三种操作：

1. 给定一个整数 $xx$，请将 $xx$ 加入到数列中。
2. 输出数列中最小的数。
3. 删除数列中最小的数（如果有多个数最小，只删除 $11$ 个）。

输入格式

第一行是一个整数，表示操作的次数 $nn$。 接下来 $nn$ 行，每行表示一次操作。每行首先有一个整数 $opop$ 表示操作类型。

• 若 $op=1op\; =\; 1$，则后面有一个整数 $xx$，表示要将 $xx$ 加入数列。
• 若 $op=2op\; =\; 2$，则表示要求输出数列中的最小数。
• 若 $op=3op\; =\; 3$，则表示删除数列中的最小数。如果有多个数最小，只删除 $11$ 个。

输出格式

对于每个操作 $22$，输出一行一个整数表示答案。

样例输入

5
1 2
1 5
2
3
2

样例输出

2
5

数据规模与约定

• 对于 $30\mathrm{\%}30\backslash \%$ 的数据，保证 $n\le 15n\; \backslash leq\; 15$。
• 对于 $70\mathrm{\%}70\backslash \%$ 的数据，保证 $n\le 10^{4}n\; \backslash leq\; 10^4$。
• 对于 $100\mathrm{\%}100\backslash \%$ 的数据，保证 $1\le n\le 10^{6}1\; \backslash leq\; n\; \backslash leq\; 10^6$，$1\le x<2^{31}1\; \backslash leq\; x\; \backslash lt\; 2^\{31\}$，$op\in \{1,2,3\}op\; \backslash in\; \backslash \{1,\; 2,\; 3\backslash \}$。

二叉堆的基本概念

二叉堆是一棵完全二叉树，结点不仅有编号，还有点权.

它一般按照二叉树的第二种存储结构实现，即：

• 根结点编号为 $11$.
• 对于编号为 $xx$ 的结点，其左子结点编号为 $2x2x$，右子结点编号为 $2x+12x+1$.
• 对于编号为 $xx$ 的结点，其父结点的编号为 $\lfloor \frac{x}{2}\rfloor \backslash left\backslash lfloor\; \backslash frac\{x\}\{2\}\backslash right\backslash rfloor$.

二叉堆一般分为小根堆和大根堆，对于一个小根堆，需要遵循如下规则：

• 以结点 $xx$ 为根的子树，其子树的所有结点的点权均小于等于结点 $xx$ 的点权.

如果是大根堆，则子树的所有结点的点权均大于等于当前结点的点权.

设二叉堆结点编号为 $xx$ 的点的点权为 $val[x]val[x]$，现在二叉堆中总共有 $tottot$ 个结点，则二叉堆支持如下几种操作.

二叉堆的堆顶元素 top()

若二叉堆是一个小根堆，则其堆顶的结点的点权 $val[1]val[1]$ 即为所有结点中点权的最小值.

若二叉堆是一个大根堆，则其堆顶的结点的点权 $val[1]val[1]$ 即为所有结点中点权的最大值.

有如下代码片段.

//代码片段-二叉堆的堆顶元素 top()
int top() {
	return val[1];
}

二叉堆的插入操作 push(p)

若二叉堆需要新添一个权值为 $pp$ 的结点，则不妨让 $tot+1tot+1$，即新增一个编号为 $tottot$ 的点权为 $pp$ 的结点.

不过，此时二叉堆并不一定满足性质，需要将其维护成满足性质的状态.

设当前结点编号为 $x=totx=tot$，则：

1. 若当前结点编号为 $11$ 即当前结点为二叉树的根结点，或者有 $val[x]⩾val\left[\lfloor \frac{x}{2}\rfloor \right]val[x]\; \backslash geqslant\; val\backslash left\; [\backslash left\backslash lfloor\; \backslash frac\{x\}\{2\}\backslash right\backslash rfloor\backslash right\; ]$，则结束维护，否则进入步骤 2.

2. 若 ，则交换 $val[x],val\left[\lfloor \frac{x}{2}\rfloor \right]val[x],\backslash ;\; val\backslash left\; [\backslash left\backslash lfloor\; \backslash frac\{x\}\{2\}\backslash right\backslash rfloor\backslash right\; ]$，并令 $x=\lfloor \frac{x}{2}\rfloor x=\backslash left\backslash lfloor\; \backslash frac\{x\}\{2\}\backslash right\backslash rfloor$，进入步骤 1.

有如下代码片段.

//代码片段-二叉堆的插入操作 push(p)
void push(int p) {
	val[++tot] = p;
	int x = tot;
	while (x != 1 && val[x] < val[x / 2]) {
		swap(val[x], val[x / 2]);
		x /= 2;
	}
}

时间复杂度分析

由于二叉堆是一棵完全二叉树，所以有 $tottot$ 个结点的二叉堆最多有 $\lfloor \log tot\rfloor +1\backslash left\backslash lfloor\backslash log\; tot\backslash right\backslash rfloor+1$ 层.

故二叉堆的插入操作的最坏时间复杂度为 $O(\log tot)O(\backslash log\; tot)$.

二叉堆的删除操作 pop()

二叉堆一般只允许删除堆顶的结点.

若二叉堆需要删除堆顶的结点，可以先让堆顶结点（编号为 $11$ 的结点）与最后一个结点（编号为 $tottot$ 的结点）的点权进行交换，随后删除最后一个结点（即让 $tot-1tot-1$）.

不过，此时二叉堆并不一定满足性质，需要将其维护成满足性质的状态.

设当前结点编号为 $x=1x=1$，则：

1. 设 $xx$ 接下来要与编号为 $sonson$ 的结点进行交换，默认 $son=2xson=2x$，进入步骤 2.
2. 若 $xx$ 的右子结点存在（即 $2x+1⩽tot2x+1\; \backslash leqslant\; tot$），并且 ，则 $son=2x+1son=2x+1$；进入步骤 3.
3. 若 $son⩽totson\; \backslash leqslant\; tot$（即要交换的结点存在），并且 $val[x]>val[son]val[x]>val[son]$，则交换点权后令 $x=sonx=son$，进入步骤 1.；否则结束维护.

有如下代码片段.

//代码片段-二叉堆的删除操作 pop()
void pop() {
	swap(val[1], val[tot]); tot--;
	int x = 1;
	while (1) {
		int son = 2 * x;
		if (2 * x + 1 <= tot && val[2 * x + 1] < val[son]) son = 2 * x + 1;
		if (son <= tot && val[x] > val[son]) {
			swap(val[x], val[son]);
			x = son;
		} else break;
	}
}

时间复杂度分析

由于二叉堆是一棵完全二叉树，所以有 $tottot$ 个结点的二叉堆最多有 $\lfloor \log tot\rfloor +1\backslash left\backslash lfloor\backslash log\; tot\backslash right\backslash rfloor+1$ 层.

故二叉堆的删除操作的最坏时间复杂度为 $O(\log tot)O(\backslash log\; tot)$.

代码实现

如下为数组模拟二叉堆的参考代码.

//洛谷 P3378 【模板】堆
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int val[N], tot;
int top() {
	return val[1];
}
void push(int p) {
	val[++tot] = p;
	int x = tot;
	while (x != 1 && val[x] < val[x / 2]) {
		swap(val[x], val[x / 2]);
		x /= 2;
	}
}
void pop() {
	swap(val[1], val[tot]); tot--;
	int x = 1;
	while (1) {
		int son = 2 * x;
		if (2 * x + 1 <= tot && val[2 * x + 1] < val[son]) son = 2 * x + 1;
		if (son <= tot && val[x] > val[son]) {
			swap(val[x], val[son]);
			x = son;
		} else break;
	}
}
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int n; cin >> n;
	while (n--) {
		int op; cin >> op;
		if (op == 1) {
			int x; cin >> x;
			push(x);
		} else if (op == 2) cout << top() << '\n';
		else pop();
	}
	return 0;
}

时间复杂度分析

最多有 $nn$ 个结点，故时间复杂度最坏为 $O(n\log n)O(n\backslash log\; n)$.

1.4.3 STL priority_queue（优先队列）¹

C++ STL中有封装好的优先队列（priority_queue）容器，其作用与二叉堆相同（默认优先队列为大根堆），引用 queue 头文件即可使用，其有如下几种基本操作：

• priority_queue<T> q：定义存储元素的数据类型为 T 的优先队列变量，其变量名为 q.
• q.top()：返回优先队列 q 队首（堆顶）元素.
• q.push(x)：将 x 放入优先队列 q 中，时间复杂度为 $O(\log n)O(\backslash log\; n)$，其中 $nn$ 为优先队列 q 内的元素个数.
• q.pop()：将优先队列 q 队首（堆顶）元素删除，时间复杂度为 $O(\log n)O(\backslash log\; n)$，其中 $nn$ 为优先队列 q 内的元素个数.
• q.size()：返回优先队列队列 q 内的元素个数.
• q.empty()：检查优先队列 q 是否为空，若优先队列 q 中没有元素则返回 true，否则返回 false.

使用 q.top()、q.pop() 这类直接调用优先队列内元素的函数时，要注意先判断优先队列是否为空.

如果优先队列为空就使用这些函数会导致程序运行时错误（Runtime Error）.

如果想让优先队列作为小根堆使用，可以考虑存储的元素均为原本元素的负值，这样就由大根堆变为了小根堆.

代码实现

如下为使用优先队列的参考代码.

//洛谷 P3378 【模板】堆 - STL priority_queue
#include<bits/stdc++.h>
using namespace std;
priority_queue<int>q;
int main(){
	ios::sync_with_stdio(0); cin.tie(0);
	int n; cin>>n;
	while(n--){
		int op; cin>>op;
		if(op==1){
			int x; cin>>x;
			q.push(-x); 
		} 
		else if(op==2) cout<<-q.top()<<'\n';
		else if(op==3) q.pop();
	}
	return 0;
}

时间复杂度分析

时间复杂度最坏为 $O(n\log n)O(n\backslash log\; n)$.

当优先队列内需要存储的元素是复合数据类型时，一般有三种处理方法：

结构体+重载运算符

优先队列是使用小于号 < 来对元素的大小进行判断的，所以当元素的数据类型是复合数据类型时，可以使用结构体加重载运算符的方式来明确优先队列内元素的大小顺序.

有如下代码片段.

//代码片段-二维元素小根堆
#include<bits/stdc++.h>
using namespace std;
struct node {
	int x, y;
	bool operator < (const node a) const {
		if (a.x == x) return y > a.y;
		else return x > a.x;
	}
};
priority_queue<node>q;
int main() {
	q.push({2, 1});
	q.push({1, 2});
	q.push({2, 3});
	q.push({1, 3});
	while (!q.empty()) {
		node now = q.top(); q.pop();
		cout << now.x << ' ' << now.y << '\n';
	}
	return 0;
}
/*
	运行结果：
	1 2
	1 3
	2 1
	2 3
*/

优先队列中，若默认为大根堆，则使用重载运算符时，元素的交换规则如下：

• 若返回 true，则说明比较的两个元素需要交换.
• 若返回 false，则说明比较的两个元素无需交换.

若优先队列是小根堆，则元素的交换规则与此相反.

使用其他可以进行比较的 STL 容器

例如 pair<T1,T2>、vector、array 等都是可以直接同种数据类型之间比较大小的，所以用它们作为优先队列内的元素时，直接按照它们的比较规则即可.

如定义

priority_queue<array<int,3>>q;

即定义了一个元素类型为 array<int,3>，即优先队列 q 内每个元素都是长度为 $33$ 的 STL array（数组）的元素.

而 array<int,3> 会按照字典序的比较方式来确定元素之间的大小.

设置优先队列的参数

可以定义

priority_queue<T,vector<T>,less<T>>;

来创建一个元素类型为 T 的大根堆（如果 T 是一个结构体，仍需要使用重载运算符确定元素之间的大小.

可以定义

priority_queue<T,vector<T>,greater<T>>;

来创建一个元素类型为 T 的小根堆.

优先队列 习题

洛谷 P1168 中位数

时间限制：1.00s　　内存限制：128.00MB

题目描述

给定一个长度为 $NN$ 的非负整数序列 $AA$，对于前奇数项求中位数。

输入格式

第一行一个正整数 $NN$。

第二行 $NN$ 个正整数 $A_{1\dots N}A\_\{1\backslash dots\; N\}$。

输出格式

共 $\lfloor \frac{N+1}{2}\rfloor \backslash lfloor\; \backslash frac\{N\; +\; 1\}2\backslash rfloor$ 行，第 $ii$ 行为 $A_{1\dots 2i-1}A\_\{1\backslash dots\; 2i\; -\; 1\}$ 的中位数。

样例输入

7
1 3 5 7 9 11 6

样例输出

1
3
5
6

提示

对于 $20\mathrm{\%}20\backslash \%$ 的数据，$N\le 100N\; \backslash le\; 100$；

对于 $40\mathrm{\%}40\backslash \%$ 的数据，$N\le 3000N\; \backslash le\; 3000$；

对于 $100\mathrm{\%}100\backslash \%$ 的数据，$1\le N\le 1000001\; \backslash le\; N\; \le \; 100000$，$0\le A_i\le 10^{9}0\; \backslash le\; A\_i\; \backslash le\; 10^9$。

题解

本题有很多种解法，这里介绍比较经典的对顶堆解法.

定义两个优先队列，一个大根堆 $q_{L}q\_L$，一个小根堆 $q_{R}q\_R$.

枚举序列，设当前已经枚举到了当前序列的第 $ii$ 个元素 $A_{i}A\_i$，则大根堆 $q_{L}q\_L$ 存储的是序列前 $1\sim i-11\backslash sim\; i-1$ 个元素的从小到大排名前 $\lceil \frac{i-1}{2}\rceil \backslash left\backslash lceil\backslash frac\{i-1\}\{2\}\backslash right\backslash rceil$ 个元素，而 $q_{R}q\_R$ 存储的是排名后 $\lfloor \frac{i-1}{2}\rfloor \backslash left\backslash lfloor\; \backslash frac\{i-1\}\{2\}\backslash right\; \backslash rfloor$ 个元素，有：

• 若 $q_{R}q\_R$ 为空或者 $A_i⩽q_R\mathrm{.}top()A\_i\; \backslash leqslant\; q\_R.top()$，则 $q_L\mathrm{.}push(A_i)q\_L.push(A\_i)$；否则 $q_R\mathrm{.}push(A_i)q\_R.push(A\_i)$.
• 随后检查是否满足 $q_L\mathrm{.}size()⩾q_R\mathrm{.}size()q\_L.size()\; \backslash geqslant\; q\_R.size()$，若不满足则需要调整两个堆使它们满足该条件.

经过这样的操作后，$q_{L}q\_L$ 内存储的就是序列排名前 $\lceil \frac{i}{2}\rceil \backslash left\backslash lceil\backslash frac\{i\}\{2\}\backslash right\backslash rceil$ 个元素，而 $q_{R}q\_R$ 内存储的就是序列排名后 $\lceil \frac{i}{2}\rceil \backslash left\backslash lceil\backslash frac\{i\}\{2\}\backslash right\backslash rceil$ 个元素.

若 $q_L\mathrm{.}size()≠q_R\mathrm{.}size()q\_L.size()\; \backslash not=\; q\_R.size()$，说明存储了前奇数项的序列了，则需要输出中位数，这个中位数就是 $q_L\mathrm{.}top()q\_L.top()$.

代码实现

在实现时，小根堆 $q_{R}q\_R$ 使用存负值的方法实现，如下为参考代码.

//洛谷 P1168 中位数 - 对顶堆写法
#include<bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;
    priority_queue<int>qL, qR;
    for (int i = 1; i <= n; ++i) {
        int a; cin >> a;
        if (qR.empty() || a <= -qR.top()) qL.push(a);
        else qR.push(-a);
        if (qL.size() < qR.size()) {
            qL.push(-qR.top());
            qR.pop();
        } else if (qL.size() - 1 > qR.size()) {
            qR.push(-qL.top());
            qL.pop();
        }
        if (qL.size() != qR.size())
            cout << qL.top() << '\n';
    }
    return 0;
}

时间复杂度分析

时间复杂度为 $O(n\log n)O(n\; \backslash log\; n)$.

以下题目会在后继章节补充.

• 洛谷 P1090 [NOIP2004 提高组] 合并果子 / [USACO06NOV] Fence Repair G

• 洛谷 P2085 最小函数值

• 洛谷 P2827 [NOIP2016 提高组] 蚯蚓

• 洛谷 P3045 [USACO12FEB]Cow Coupons G