From 59eb9e653a07a7b38d32d713f92ff7eddfe57c1b Mon Sep 17 00:00:00 2001
From: ZJsonJun <zhangjun5469@gmail.com>
Date: Sat, 16 Jan 2021 19:37:35 +0800
Subject: [PATCH] Update binary-heap.md
MIME-Version: 1.0
Content-Type: text/plain; charset=utf8
Content-Transfer-Encoding: 8bit

关于堆顶对的讨论，原始页面有错误，主要错误在于对于小顶堆和大顶堆所存储元素的大小关系认识偏差。已帮忙修改。
应该是小顶堆存大值， 大顶堆存小值。这里要求第k大的话，应该是维护小顶堆的大小为k；
当插入元素时，如果元素比小顶堆的堆顶元素大，则插入小顶堆；否则插入大顶堆；之后再维护堆大小
查询第k大元素即是小顶堆堆顶元素
---
 docs/ds/binary-heap.md | 22 +++++++++++-----------
 1 file changed, 11 insertions(+), 11 deletions(-)

diff --git a/docs/ds/binary-heap.md b/docs/ds/binary-heap.md
index 678188f8..73713df3 100644
--- a/docs/ds/binary-heap.md
+++ b/docs/ds/binary-heap.md
@@ -140,17 +140,17 @@ $$
 
 对于此类问题，我们可以使用 **对顶堆** 这一技巧予以解决（可以避免写权值线段树或 BST 带来的繁琐）。
 
-对顶堆由一个大根堆与一个小根堆组成，大根堆维护第 $k$ 大以及之前的数，小根堆维护第 $k$ 大之后的数。
+对顶堆由一个大根堆与一个小根堆组成，小根堆维护大值即前 $k$ 大的值（包含第k个），大根堆维护小值即比第 $k$ 大数小的其他数。
 
 这两个堆构成的数据结构支持以下操作：
 
-- 维护：当大根堆的大小小于 $k$ 时，不断将小根堆堆顶元素取出并插入大根堆，直到大根堆的大小等于 $k$ ；当大根堆的大小大于 $k$ 时，不断将大根堆堆顶元素取出并插入小根堆，直到大根堆的大小等于 $k$ ；
-- 插入元素：若插入的元素小于等于大根堆堆顶元素，则将其插入大根堆，否则将其插入小根堆，然后维护对顶堆；
-- 查询第 $k$ 大元素：大根堆堆顶元素即为所求；
-- 删除第 $k$ 大元素：删除大根堆堆顶元素，然后维护对顶堆；
+- 维护：当小根堆的大小小于 $k$ 时，不断将大根堆堆顶元素取出并插入小根堆，直到小根堆的大小等于 $k$ ；当小根堆的大小大于 $k$ 时，不断将小根堆堆顶元素取出并插入大根堆，直到小根堆的大小等于 $k$ ；
+- 插入元素：若插入的元素大于等于小根堆堆顶元素，则将其插入小根堆，否则将其插入大根堆，然后维护对顶堆；
+- 查询第 $k$ 大元素：小根堆堆顶元素即为所求；
+- 删除第 $k$ 大元素：删除小根堆堆顶元素，然后维护对顶堆；
 -  $k$ 值 $+1/-1$ ：根据新的 $k$ 值直接维护对顶堆。
 
-显然，查询第 $k$ 大元素的时间复杂度是 $O(1)$ 的。由于插入、删除或调整 $k$ 值后，大根堆的大小与期望的 $k$ 值最多相差 $1$ ，故每次维护最多只需对大根堆与小根堆中的元素进行一次调整，因此，这些操作的时间复杂度都是 $O(\log n)$ 的。
+显然，查询第 $k$ 大元素的时间复杂度是 $O(1)$ 的。由于插入、删除或调整 $k$ 值后，小根堆的大小与期望的 $k$ 值最多相差 $1$ ，故每次维护最多只需对大根堆与小根堆中的元素进行一次调整，因此，这些操作的时间复杂度都是 $O(\log n)$ 的。
 
 ??? "参考代码"
 
@@ -165,22 +165,22 @@ $$
         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())
+                    if (a.empty() || x >= a.top())
                         a.push(x);
                     else
                         b.push(x);
-- 
2.11.0