模拟堆
维护一个集合,初始时集合为空,支持如下几种操作:
- “I x”,插入一个数x;
- “PM”,输出当前集合中的最小值;
- “DM”,删除当前集合中的最小值(数据保证此时的最小值唯一);
- “D k”,删除第k个插入的数;
- “C k x”,修改第k个插入的数,将其变为x;
现在要进行N次操作,对于所有第2个操作,输出当前集合的最小值。
输入样例
8
I -10
PM
I -10
D 1
C 2 8
I 6
PM
DM
输出样例
-10
6
代码
#include<iostream>
#include<algorithm>
#include<stdio.h>
using namespace std;
typedef long long LL;
const int N = 1e5+10;
int h[N], hsize;
int ph[N], hp[N];//ph存放第k个插入点的下标,hp存放堆中点的插入次序
void heap_swap(int u, int v)//三者存在映射关系,必须同时交换
{
swap(h[u], h[v]);
swap(hp[u], hp[v]);
swap(ph[hp[u]], ph[hp[v]]);
}
void down(int x)
{
int min = x;
if (x * 2 <= hsize && h[x * 2] < h[min])
min = x * 2;
if (x * 2 + 1 <= hsize && h[x * 2 + 1] < h[min])
min = x * 2 + 1;
if (x != min)
{
heap_swap(x,min);
down(min);
}
}
void up(int x)
{
if (x / 2 > 0 && h[x] < h[x / 2])
{
heap_swap(x, x / 2);
up(x >> 1);//每个父节点和子节点之间差两倍
}
}
int main()
{
int n,m=0;//m记录是第几个插入的
cin >> n;
while (n--)
{
string op;
int k, x;
cin >> op;
if (op == "I")
{
scanf("%d", &x);
hsize++;
m++;
ph[m] = hsize;//记录下标
hp[hsize] = m;//记录次序
h[hsize] = x;//记录值
up(hsize);
}
else if (op=="PM")
{
printf("%d\n", h[1]);
}
else if (op=="DM")
{
heap_swap(1, hsize);
hsize--;
down(1);
}
else if (op=="D")
{
scanf("%d", &k);
int u = ph[k];//保存下标,因为之后ph[k]的值会改变
heap_swap(u, hsize);//和最后一个元素交换
hsize--;
down(u);//必定只会执行一个函数
up(u);
}
else if(op=="C")
{
scanf("%d%d", &k, &x);
h[ph[k]] = x;
down(ph[k]);
up(ph[k]);
}
}
return 0;
}
堆排序
共一行,包含m个整数,表示整数数列中前m小的数。
输入样例
5 3
4 5 1 3 2
输出样例
1 2 3
代码
#include<iostream>
#include<algorithm>
#include<stdio.h>
using namespace std;
typedef long long LL;
const int N = 1e5+10;
int h[N], hsize;
void down(int x)
{
int min = x;
if (x * 2 <= hsize && h[x * 2] < h[min])
min = x * 2;
if (x * 2 + 1 <= hsize && h[x * 2 + 1] < h[min])
min = x * 2 + 1;
if (x != min)
{
swap(h[x], h[min]);
down(min);
}
}
int main()
{
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++)
scanf("%d", &h[i]);
hsize = n;
for (int i = n / 2; i; i--)//把较大的数往下移
down(i);
while (m--)
{
printf("%d ", h[1]);
h[1] = h[hsize];//用最后一个数覆盖根节点
hsize--;//总数减一
down(1);
}
return 0;
}