如何用模拟堆解决Acwing第839题？
摘要：35.Acwing基础课第839题-简单-模拟堆 题目描述 输入一个长度为 n 的整数数列，从小到大输出前 m 小的数。 输入格式 第一行包含整数 n 和 m。 第二行包含 n 个整数，表示整数数列。 输出格式 共一行，包含 m 个整数，表
35.Acwing基础课第839题-简单-模拟堆
题目描述
输入一个长度为 n 的整数数列，从小到大输出前 m 小的数。
输入格式
第一行包含整数 n 和 m。
第二行包含 n 个整数，表示整数数列。
输出格式
共一行，包含 m 个整数，表示整数数列中前 m 小的数。
数据范围
\(1≤m≤n≤10^5\)
\(1≤数列中元素≤10^9\)
输入样例：
5 3
4 5 1 3 2
输出样例：
1 2 3
代码：
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
const int N = 100010;
int h[N]; // 堆数组（1-based）
int ph[N]; // ph[k]：第k个插入的数 → 堆中的下标u
int hp[N]; // hp[u]：堆下标u → 第k个插入的数
int cnt; // 堆的当前大小
int idx; // 插入序号（第1、2...个插入）
// 自定义swap：同步维护堆值+ph+hp（核心！必须先swap映射，再swap值）
void heap_swap(int a, int b)
{
swap(ph[hp[a]], ph[hp[b]]); // 交换“插入序号→堆下标”
swap(hp[a], hp[b]); // 交换“堆下标→插入序号”
swap(h[a], h[b]); // 交换堆值
}
// down操作（仅调用heap_swap）
void down(int u)
{
int t = u;
if (u*2 <= cnt && h[u*2] < h[t]) t = u*2;
if (u*2+1 <= cnt && h[u*2+1] < h[t]) t = u*2+1;
if (u != t)
{
heap_swap(u, t);
down(t);
}
}
// up操作（仅调用heap_swap）
void up(int u)
{
while (u/2 && h[u] < h[u/2]) // u/2>0 等价于 u/2
{
heap_swap(u, u/2);
u /= 2;
}
}
// 插入：I x
void heap_insert(int x)
{
idx++; // 插入序号+1
cnt++; // 堆大小+1
ph[idx] = cnt; // 第idx个插入 → 堆下标cnt
hp[cnt] = idx; // 堆下标cnt → 第idx个插入
h[cnt] = x; // 堆尾赋值
up(cnt); // 上浮
}
// 查询最小值：PM
int heap_get_min()
{
return h[1];
}
// 删除最小值：DM（核心修复！必须先swap堆顶和堆尾，再删堆尾）
void heap_delete_min()
{
if (cnt == 0) return;
heap_swap(1, cnt); // 堆顶和堆尾交换（自动维护映射）
cnt--; // 删除堆尾（原堆顶）
down(1); // 新堆顶下沉
}
// 删除第k个插入的数：D k
void heap_delete_k(int k)
{
if (k < 1 || k > idx || ph[k] == 0) return; // 非法k直接返回
int u = ph[k]; // 第k个插入 → 堆下标u
heap_swap(u, cnt); // u和堆尾交换（维护映射）
cnt--; // 删除堆尾（原u位置的数）
down(u); // 调整u位置
up(u);
ph[k] = 0; // 清空映射（避免重复访问）
}
// 修改第k个插入的数：C k x
void heap_modify_k(int k, int x)
{
if (k < 1 || k > idx || ph[k] == 0) return;
int u = ph[k]; // 第k个插入 → 堆下标u
h[u] = x; // 修改值
down(u); // 调整
up(u);
}
int main()
{
ios::sync_with_stdio(false); // 加速cin/cout（避免超时）
cin.tie(0);
int n;
cin >> n;
while (n--)
{
string op;
cin >> op;
if (op == "I")
{
int x;
cin >> x;
heap_insert(x);
}
else if (op == "PM") cout << heap_get_min() << '\n';
else if (op == "DM") heap_delete_min();
else if (op == "D")
{
int k;
cin >> k;
heap_delete_k(k);
}
else if (op == "C")
{
int k, x;
cin >> k >> x;
heap_modify_k(k, x);
}
}
return 0;
}