浙师大数据结构1019，堆的建立与维护，C语言

题目：

Description

用已知的数据建立一个小顶堆，再对询问输出相应的结果。

Input

输入数据有多组
对于每组测试数据，第一行两个整数n和m ( n，m<= 10000)，表示要用n个整数要建立堆，有m个询问。第二行有n个整数。接下来m行，每行为“pop”或者“push x”表示取出堆顶元素和将x插入堆中

Output

对于“pop”询问输出一行，为堆顶元素

Sample Input

5 5

2 1 3 4 5

pop

push 3

pop

push 1

pop

Sample Output

1

2

1

问题描述

两次提交均是wrong answer,小错误一改后，run time error,开心了不少，菜鸟离胜利不远啦！

下面是C语言代码（只会比较低级的）

#include
#include
void swap(int *a,int *b)
{ int t;
  t=*a;
  *a=*b;
  *b=t;	
}
void HeadAdjust(int *a,int l,int k)
{ int i;
  a[0]=a[k];
  for(i=2*k;i<=l;i*=2)
  { if(ia[i+1]) i++;
    if(a[k]=1;i--)
  HeadAdjust(a,l,i);
	
}
int main()
{ int n,m;  
  while(scanf("%d%d",&n,&m)!=EOF)
{  int l=n;
  int i,j,a[15000];//第三个错误
  for(i=1;i<=n;i++)
  scanf("%d",&a[i]);
  BuildMinHeap(a,l);
  for(j=0;j

---

一处原因分析：

对于第一个错误，没考虑到他要是一直要pop的情况，所以其实每次pop后除了要让数组前移之外，还要再进行一次BuildMinHead,以让下次pop的时候还是输出最小值

例如，输入是

3 2

5 6 3

pop

pop

在不加那一句的时候输出就是 3  6（因为每次输出是a[1],上次pop后6刚好移到了a[1]）

加了那一句就是 3  5    正确！

---

二处和三处原因分析：

很简单的忘记了l++和++l（我在写的时候还想着呢）

第三处，最初设定a数组是a[n+1]，但是后来每次都会push呀！，所以改大一点就好啦

欢迎分享，转载请注明来源：内存溢出

原文地址:https://54852.com/langs/1325662.html