ch03 - 二叉堆

二叉堆判定

• 详见课本 【例3.1】二叉堆的判定

二叉堆 I

• 详见课本 【例3.2】二叉堆模板题

前缀第 k 小

• 详见课本 【例3.3】前缀第 k 小

前缀中位数

• 详见课本 【例3.4】前缀中位数

区间中位数

• 知识点：对顶堆、multiset 的使用

• 思路：

  • 对顶堆通常使用优先队列实现，它允许插入元素并查询第 k 小的值。但如果需要删除特定元素，优先队列并不提供直接的方法
  • 对顶堆的核心在于能够快速插入数据并进行排序。除了优先队列，其他如 set、map、multiset 等容器也能实现快速插入并排序，并且它们还支持快速删除任意元素
  • 在本题中，使用 multiset 容器来替代对顶堆模板中的优先队列，并实现了删除元素的功能

• 代码：

  #include <bits/stdc++.h>
  using namespace std;
  
  // l 替换 qmax、r 替换 qmin
  multiset<int> l, r;
  // 插入和查询的逻辑同对顶堆
  void insert(int x) {
      if (!l.empty() && x < *l.rbegin()) {
          l.insert(x);
      } else {
          r.insert(x);
      }
  }
  int query(int k) {
      while (l.size() > k) {
          r.insert(*l.rbegin());
          l.erase(--l.end());
      }
      while (l.size() < k) {
          l.insert(*r.begin());
          r.erase(r.begin());
      }
      return *l.rbegin();
  }
  
  int a[100010];
  int main() {
      int n, k;
      cin >> n >> k;
      for (int i = 1; i <= n; ++i) {
          cin >> a[i];
          insert(a[i]);
          if (i >= k) {
              cout << query((k + 1) / 2) << endl;
              // 添加删除操作
              if (l.find(a[i - k + 1]) != l.end())
                  l.erase(l.find(a[i - k + 1]));
              else
                  r.erase(r.find(a[i - k + 1]));
          }
      }
      return 0;
  }
  

黑匣子

• 知识点：对顶堆、模拟

• 思路：

  • 在一个空的黑匣子中依次加入元素 a[i]，并在加入第 u[i] 个元素时执行一次 I+1 操作（初始 I 为0），然后输出第 I 小的元素

  • 可以使用对顶堆来实现这一查询操作

• 代码：

  // cnt[i]: a[i] 插入后要立即执行的 GET 次数
  int a[200010], cnt[200010];
  int main() {
      int m, n, u, I = 0;
      cin >> m >> n;
      for (int i = 1; i <= m; ++i) cin >> a[i];
      for (int i = 1; i <= n; ++i) cin >> u, ++cnt[u];
      for (int i = 1; i <= m; ++i) {
          insert(a[i]);
          for (int j = 1; j <= cnt[i]; ++j) {
              cout << query(++I) << "\n";
          }
      }
      return 0;
  }
  

直播获奖

• 知识点：对顶堆、第 k 大

• 思路：排名前 $w$ 的选手可以获奖，那么在第 $i$ 个选手时，需要查询第 k = max(1, i * w / 100) 大的元素，这等价于查询第 i-k+1 小的元素

• 代码：

  // ... 对顶堆模板此处省略
  int main() {
      int n, w, x;
      cin >> n >> w;
      for (int i = 1; i <= n; ++i) {
          cin >> x;
          insert(x);
          // 第 k 大
          int k = max(1, i * w / 100);
          // 第 i - k + 1 小
          cout << query(i - k + 1) << " ";
      }
      return 0;
  }
  

二叉堆 II

• 知识点：二叉堆的模拟

• 思路：

  • 本题难点在于清晰区分输入数组 a 的下标、二叉堆的下标（即节点编号）以及节点的权值，确保不会混淆这三者

  • 维护一个 ind 数组，用于记录数组 a 中每个数值在二叉堆 heap 中的位置

  • 注意：在交换二叉堆 heap 中的节点时，也必须同步交换它们在 ind 数组中的位置

• 代码：

  #include <bits/stdc++.h>
  using namespace std;
  
  const int maxn = 100010;
  // heap[i]: 存储 存在该位置的 a[x] 的下标 x
  int heap[maxn];
  // ind[i]: i 在 heap 中的位置
  int a[maxn], ind[maxn];
  // 除了交换 heap[x], heap[y]，还需要把 x 与 y 在 heap 中的位置也进行交换
  void _swap(int x, int y) {
      swap(heap[x], heap[y]);
      swap(ind[heap[x]], ind[heap[y]]);
  }
  int tot;
  int up(int u) {
      // 不为根节点 且 子节点值 < 父节点值
      // heap[i] 存储的是下标，值为 a[heap[i]]
      while (u != 1 && a[heap[u]] < a[heap[u / 2]]) {
          _swap(u, u / 2);
          u = u / 2;
      }
      return u;
  }
  int ins(int p) {
      heap[++tot] = p;
      ind[p] = tot;
      return up(tot);
  }
  void down(int u) {
      while (u * 2 <= tot) {
          int l = u * 2, r = l + 1;
          // 如果有右儿子，且右儿子比左儿子大，则使用右儿子与当前节点比较
          if (r <= tot && a[heap[r]] < a[heap[l]]) swap(l, r);
          if (a[heap[u]] > a[heap[l]]) {
              _swap(u, l);
              u = l;
          } else
              break;
      }
  }
  void del(int p) {
      _swap(p, tot);
      --tot;
      // 注意：删除一个中间的节点，除了下沉，还可以上浮
      up(p);
      down(p);
  }
  int main() {
      int n, q, op, x;
      cin >> n >> q;
      for (int i = 1; i <= n; ++i) cin >> a[i];
      while (q--) {
          cin >> op >> x;
          if (op == 1) {
              cout << ins(x) << endl;
          } else if (op == 2) {
              cout << ind[x] << endl;
              del(ind[x]);
              ind[x] = 0;
          }
      }
      return 0;
  }
  

二叉堆 III

• 知识点：二叉堆的模拟

• 思路：

  • 本题难点在于清晰区分输入数组 a 的下标、二叉堆的下标（即节点编号）以及节点的权值，确保不会混淆这三者
  • 在理解了“二叉堆 II”后，本题中的 up 和 down 操作保持不变
  • 新增了修改节点值的操作：若需在堆中减小某个数值，只需对该节点执行上浮操作

• 代码：

  // ... 代码与二叉堆 II 相同，除了新增 update 函数 ...
  // update 函数用于修改节点值，并执行上浮操作以维持二叉堆
  void update(int p, int x) {
      a[p] = x;
      up(ind[p]);
  }
  int main() {
      int n, q, op, x, y;
      cin >> n >> q;
      for (int i = 1; i <= n; ++i) cin >> a[i];
      while (q--) {
          cin >> op;
          if (op == 1) {
              cin >> x;
              cout << ins(x) << endl;
          } else if (op == 2) {
              cin >> x >> y;
              update(x, y);
              cout << ind[x] << endl;
          } else {
              cout << heap[1] << endl;
              del(1);
          }
      }
      return 0;
  }