请按照以下要求写一段c语言代码:描述 定义一个数组,初始化为空。在数组上执行两种操作: 1、增添1个元素,把1个新的元素放入数组。 2、输出并删除数组中最小的数。 使用堆结构实现上述功能的高效算法。 输入 第一行输入一个整数t,代表测试数据的组数。 对于每组测试数据,第一行输入一个整数n,代表操作的次数。 每次操作首先输入一个整数type。 当type=1,增添操作,接着输入一个整数u,代表要插入的元素。 当type=2,输出删除操作,输出并删除数组中最小的元素。 1<=n<=100000。 输出 每次删除操作输出被删除的数字。
时间: 2023-07-14 13:13:56 浏览: 115
以下是使用堆结构实现的C语言代码:
```
#include <stdio.h>
#include <stdlib.h>
#define MAX_N 100000
int heap[MAX_N];
int heap_size = 0;
void swap(int *a, int *b) {
int tmp = *a;
*a = *b;
*b = tmp;
}
void heap_push(int x) {
int i = heap_size++;
heap[i] = x;
while (i > 0 && heap[(i - 1) / 2] > heap[i]) {
swap(&heap[i], &heap[(i - 1) / 2]);
i = (i - 1) / 2;
}
}
void heap_pop() {
printf("%d\n", heap[0]);
heap[0] = heap[--heap_size];
int i = 0;
while (2 * i + 1 < heap_size) {
int child = 2 * i + 1;
if (child + 1 < heap_size && heap[child + 1] < heap[child]) {
child++;
}
if (heap[i] > heap[child]) {
swap(&heap[i], &heap[child]);
} else {
break;
}
i = child;
}
}
int main() {
int t;
scanf("%d", &t);
while (t--) {
int n;
scanf("%d", &n);
heap_size = 0;
while (n--) {
int type, u;
scanf("%d", &type);
if (type == 1) {
scanf("%d", &u);
heap_push(u);
} else {
heap_pop();
}
}
}
return 0;
}
```
首先定义了一个数组`heap`,用于存储堆的元素,以及一个变量`heap_size`表示当前堆的大小。堆是一种完全二叉树,可以使用数组来表示,根据完全二叉树的性质,堆中第i个节点的左子节点为2i+1,右子节点为2i+2,父节点为(i-1)/2。
对于增添操作,将新的元素放入堆的末尾,然后向上比较与父节点的大小,如果比父节点小则交换,直到满足堆的性质为止。
对于输出删除操作,输出堆顶元素,将堆顶元素与末尾元素交换,然后向下比较与子节点的大小,如果比子节点大则交换,直到满足堆的性质为止。
在主函数中,首先读入测试数据的组数`t`,然后对于每组测试数据,读入操作次数`n`,在循环中根据输入的`type`执行增添或删除操作。
阅读全文