给定一个数列，初始为空，请支持下面三种操作：
- 给定一个整数 x，请将 x 加入到数列中。输出数列中最小的数。删除数列中最小的数（如果有多个数最小，只删除 1 个）。
第一行是一个整数，表示操作的次数 n。
接下来 nn 行，每行表示一次操作。每行首先有一个整数 op 表示操作类型。
若 op=1，则后面有一个整数 x，表示要将 x 加入数列。若 op=2，则表示要求输出数列中的最小数。若 op=3，则表示删除数列中的最小数。如果有多个数最小，只删除 1 个。 输出格式
对于每个操作 2，输出一行一个整数表示答案。
输入输出样例输入 #1复制
5 1 2 1 5 2 3 2
输出 #1复制
2 5说明/提示
【数据规模与约定】
对于 30% 的数据，保证 n≤15。对于 70% 的数据，保证 n≤10^4。对于 100% 的数据，保证1≤n≤10^6，1≤x<2^31，op∈{1,2,3}。
利用STL库里的优先队列实现堆 AC代码如下
#includeusing namespace std; priority_queue q;//定义降序优先队列 int n, a, b; int main() { scanf("%d", &n); for (int i = 1; i <= n; i++){ scanf("%d", &a); switch (a) { case 1: { scanf("%d", &b); q.push(-b); //把-b压入优先队列 从而实现升序，即原来最小的，取相反数后成最大的，会放在队首 break; } case 2: { int ans = q.top(); //获取队首值 printf("%dn", -ans); //输出队首相反数，因为入队时是取相反数入队 break; } case 3: { q.pop(); //将队首弹出 break; } } } return 0; }
了解优先队列priority_queue用法 可戳以下链接
c++优先队列(priority_queue)用法详解_吕白_的博客-CSDN博客_c++ 优先队列https://blog.csdn.net/weixin_36888577/article/details/79937886?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522164735761716780366536911%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=164735761716780366536911&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~baidu_landing_v2~default-1-79937886.142%5Ev2%5Earticle_score_rank,143%5Ev4%5Econtrol&utm_term=C%2B%2B+%E4%BC%98%E5%85%88%E9%98%9F%E5%88%97&spm=1018.2226.3001.4187
另外贴上手打堆代码，其实堆就是个完全二叉树，此处用到最小堆结构，只不过手打堆在此题倒数第二个测试点TLE了，虽然用的空间更小，但是其他的测试点的速度也不是非常快，总而言之还是优先队列好用。
#includeusing namespace std; int n,p,k=0; int h[1000010]; void my_swap(int x, int y) {//交换根结点和较小儿子的值 int t = h[x];//使原根结点和较小儿子的值交换 h[x] = h[y]; h[y] = t; return; } void siftdown(int i) { //使以i为根结点的树满足最小堆结构 if (i == 0)return; int t, flag = 0;//flag用来标记是否需要继续向下调整 //t用来记录每次较小的标号 while (i * 2 <= k && flag == 0) { if (h[i] > h[i * 2])//先判断和左儿子的关系 t = i * 2; else t = i; //如果它有右儿子，那就继续判断 if (i * 2 + 1 <= k) { if (h[t] > h[i * 2 + 1]) t = i * 2 + 1; } if (t != i) {//说明需要调整 my_swap(t, i); i = t; } else//否则此树已经符合最小堆结构 flag = 1; } return; } void creat() { int i; //对于有n个结点的完全二叉树来说n/2是最后一个非叶结点 //从此处开始逐个遍历以第i个结点为根结点的树 //使以为此结点为根结点的二叉树满足最小堆结构 for (int i = k / 2; i >= 1; i--) siftdown(i); } void deletemin() { int t = h[1]; h[1] = h[k]; k--; siftdown(1); return ; } int main(){ scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d", &p); if (p == 1) { scanf("%d", &h[++k]); creat();//建最小堆 } if (p == 2)printf("%dn", h[1]); if (p == 3) { deletemin(); } } return 0; }
最后贴上C语言手打堆AC代码
#include#include #include #include #include #include #define LL long long void min_down(int num[], int i, int size); void swap(int *a, int *b); void min_up(int num[], int i, int size); void min_insert(int num[], int value, int *size); void min_pop(int num[], int *size); void min_rank(int num[], int size); void min_pop(int num[], int *size); void swap(int *a, int *b) { int c = *a; *a = *b; *b = c; return; } void min_down(int num[], int i, int size) //最小堆向下更新 { int child = i * 2; while (child <= size) { if (child < size && num[child] > num[child + 1]) child++; if (num[child] < num[i]) { swap(&num[child], &num[i]); i = child; child = i * 2; } else break; } return; } void min_up(int num[], int i, int size) //最小堆向上更新 { while (i > 1) { if (num[i] < num[i / 2]) { swap(&num[i], &num[i / 2]); i /= 2; } else break; } return; } void min_insert(int num[], int value, int *size) //最小堆插入 { num[++(*size)] = value; min_up(num, *size, *size); } void min_pop(int num[], int *size) //最小堆弹出堆顶 { num[1] = num[(*size)--]; min_down(num, 1, *size); } void min_rank(int num[], int size) //堆排序 自大到小 { for (int i = size; i >= 2;) { swap(&num[1], &num[i--]); min_down(num, 1, i); } return; } void min_bulid(int num[], int size) { for (int i = size / 2; i >= 1; i--) min_down(num, i, size); } int num[1000010]; int main() { int n; scanf("%d", &n); int size = 0; while (n--) { int op; scanf("%d", &op); if (op == 1) { int x; scanf("%d", &x); min_insert(num, x, &size); } else if (op == 2) printf("%dn", num[1]); else min_pop(num, &size); } return 0; }
