From b521921a33bc03ffde99bcb457f5a81a3a64ff8c Mon Sep 17 00:00:00 2001
From: sbofgayschool <1532422769@qq.com>
Date: Sun, 20 Dec 2020 10:41:02 +0800
Subject: [PATCH] Added median maintenance as an application of heap.

---
 docs/ds/binary-heap.md                 | 79 ++++++++++++++++++++++++++++++++++
 docs/lang/csl/associative-container.md |  4 +-
 2 files changed, 81 insertions(+), 2 deletions(-)

diff --git a/docs/ds/binary-heap.md b/docs/ds/binary-heap.md
index 13dfeac1..03fc97ee 100644
--- a/docs/ds/binary-heap.md
+++ b/docs/ds/binary-heap.md
@@ -123,3 +123,82 @@ $$
 之所以能 $O(n)$ 建堆，是因为堆性质很弱，二叉堆并不是唯一的。
 
 要是像排序那样的强条件就难说了。
+
+### 应用
+
+#### 对顶堆
+
+??? note "[SP16254 RMID2 - Running Median Again](https://www.luogu.com.cn/problem/SP16254)"
+	维护一个序列，支持两种操作：
+	
+	1. 向序列中插入一个元素
+	
+	2. 输出并删除当前序列的中位数（若序列长度为偶数，则输出较小的中位数）
+
+这个问题可以被进一步抽象成：动态维护一个序列上第 $k$ 大的数，$k$ 值可能会发生变化。
+
+对于此类问题，我们可以使用 **对顶堆** 这一技巧予以解决（可以避免写权值线段树或BST带来的繁琐）。
+
+对顶堆由一个大根堆与一个小根堆组成，大根堆维护第 $k$ 大以及之前的数，小根堆维护第 $k$ 大之后的数。
+
+这两个堆构成的数据结构支持以下操作：
+
+- 维护：当大根堆的大小小于 $k$ 时，不断将小根堆堆顶元素取出并插入大根堆，直到大根堆的大小等于 $k$；当大根堆的大小大于 $k$ 时，不断将大根堆堆顶元素取出并插入小根堆，直到大根堆的大小等于 $k$；
+- 插入元素：若插入的元素小于等于大根堆堆顶元素，则将其插入大根堆，否则将其插入小根堆，然后维护对顶堆；
+- 查询第 $k$ 大元素：大根堆堆顶元素即为所求；
+- 删除第 $k$ 大元素：删除大根堆堆顶元素，然后维护对顶堆；
+- $k$ 值 $+1/-1$ ：根据新的 $k$ 值直接维护对顶堆；
+
+显然，查询查询第 $k$ 大元素的时间复杂度时 $O(1)$ 的。由于插入、删除或调整 $k$ 值后，大根堆的大小与期望的 $k$ 值最多相差 $1$，故每次维护最多只需对大根堆与小根堆中的元素进行一次调整，因此，这些操作的时间复杂度都是 $O(\log n)$ 的。
+
+??? "参考代码"
+	```cpp
+	#include <iostream>
+	#include <cstdio>
+	#include <queue>
+	using namespace std;
+	int t, x;
+	int main()
+	{
+	    scanf("%d", &t);
+	    while (t--)
+	    {
+	        // 大根堆，维护前一半元素
+	        priority_queue<int, vector<int>, less<int> > a;
+	        // 小根堆，维护后一半元素
+	        priority_queue<int, vector<int>, greater<int> > b;
+	        while (scanf("%d", &x) && x)
+	        {
+	            // 若为查询并删除操作，输出并删除小根堆堆顶元素
+	            if (x == -1)
+	            {
+	                printf("%d\n", a.top());
+	                a.pop();
+	            }
+	            // 若为插入操作，根据小根堆堆顶的元素值，选择合适的堆进行插入
+	            else
+	            {
+	                if (a.empty() || x <= a.top())
+	                    a.push(x);
+	                else
+	                    b.push(x);
+	            }
+	            // 对堆顶堆进行调整
+	            if (a.size() > (a.size() + b.size() + 1) / 2)
+	            {
+	                b.push(a.top());
+	                a.pop();
+	            }
+	            else if (a.size() < (a.size() + b.size() + 1) / 2)
+	            {
+	                a.push(b.top());
+	                b.pop();
+	            }
+	        } 
+	    }
+		return 0;
+	}
+	```
+
+- 双倍经验：[SP15376 RMID - Running Median](https://www.luogu.com.cn/problem/SP15376)
+- 典型习题：[P1801 黑匣子](https://www.luogu.com.cn/problem/P1801)
diff --git a/docs/lang/csl/associative-container.md b/docs/lang/csl/associative-container.md
index 0e6d5667..75651810 100644
--- a/docs/lang/csl/associative-container.md
+++ b/docs/lang/csl/associative-container.md
@@ -51,7 +51,7 @@
 
 ### 使用样例
 
-#####  `set` 在贪心中的使用
+####  `set` 在贪心中的使用
 
 在贪心算法中经常会需要出现类似 **找出并删除最小的大于等于某个值的元素** 。这种操作能轻松地通过 `set` 来完成。
 
@@ -120,7 +120,7 @@ map<string, int> mp;
 
 ### 使用样例
 
-#####  `map` 用于存储复杂状态
+####  `map` 用于存储复杂状态
 
 在搜索中，我们有时需要存储一些较为复杂的状态（如坐标，无法离散化的数值，字符串等）以及与之有关的答案（如到达此状态的最小步数）。 `map` 可以用来实现此功能。其中的键是状态，而值是与之相关的答案。下面的示例展示了如何使用 `map` 存储以 `string` 表示的状态。
 
-- 
2.11.0