P3378 【模板】堆
题目描述
给定一个初始为空的数列,请支持以下三种操作:
1.给定一个整数 x,将 x 加入数列中;
2.输出数列中最小的数;
3.删除数列中最小的数。如果有多个数都是最小的,只删除其中的一个。
一共要进行 n 次操作,请你按照输入给出的顺序依次执行这些操作,并对每一次操作 2 给出回答。
输入格式
第一行输入一个整数 n(1≦n≦106) 代表操作的次数。
此后 n 行,第 i 行输入一次操作,每行先输入一个整数 op(1≦op≦3) 代表操作类型,编号同题干:
∙若 op=1,紧接着在同一行输入一个整数 x(1≦x<231) 代表要加入数列的数;
∙若 op=2,该行只有 op 一个整数;
∙若 op=3,该行只有 op 一个整数。
保证当 op=2 或 op=3 时,数列不为空。
输出格式
对于每一次 op=2 的操作,新起一行输出一个整数,代表当时数列中最小的数。
测试样例
5
1 2
1 5
2
3
2
2
5
样例 1 解释
依次执行 5 次操作,数列的变化如下:
∙操作 1(x=2):数列变为 {2};
∙操作 1(x=5):数列变为 {2,5};
∙操作 2:数列中最小的数是 2,输出 2;
∙操作 3:删除数列中最小的数 2,数列变为 {5};
∙操作 2:数列中最小的数是 5,输出 5。
因此依次输出 2 和 5。
8
1 4
1 2
2
1 6
3
2
3
2
2
4
6
提示
对于 30% 的数据,n≦15;
对于 70% 的数据,n≦104;
对于 100% 的数据,1≦n≦106,1≦x<231,op∈{1,2,3}。