题目描述
blablabla
样例
#include<iostream>
#include<cstring>
using namespace std;
const int N=1010;//最多十万个数据 因此用scf
int h[N];
int n;
void dfs(int u)//后续遍历最后输出根节点
{
if(u*2<=n) dfs(u*2);//有左子树先遍历左子树
if(u*2+1<=n) dfs(u*2+1);//需要前面声明过n才能用n
printf("%d",h[u]);//可以直接写h[u];
if(u!=1) printf(" ");//需要空格,最后不需要空格
}
int main()
{
int T;
scanf("%d %d",&T,&n);
while(T--)
{
for(int i=1;i<=n;i++) scanf("%d",&h[i]);//从1开始存
bool lt=false,gt=false;//两个变量表示出现小于关系、出现大于关系
for(int i=1;i<=n;i++)
{
for(int j=0;j<2;j++)//左右儿子2*i+j
if(i*2+j<=n)//存在儿子
{
int a=h[i],b=h[2*i+j];
if(a<b) lt=true;//儿子大
else gt=true;//题中说明没有相同的元素 因此只有大于小于
}//只有全是lt=true或者全是gt=true 只要有一次遍历使得另一个bool变正那么就不是堆了
}
if(lt && gt) puts("Not Heap");//puts结尾自动有换行
else if(lt) puts("Min Heap");
else if(gt) puts("Max Heap");
dfs(1);
printf("\n");//puts("")表示回车
}
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
#include<iostream>
using namespace std;
const int N=1010;
int h[N];
int n,m;
void dfs(int u)
{
if(2*u<=n) dfs(2*u);//有左儿子
if(2*u+1<=n) dfs(2*u+1);
printf("%d",h[u]);
if(u!=1) printf(" ");
}
int main()
{
scanf("%d %d",&m,&n);
while(m--)
{
for(int i=1;i<=n;i++) scanf("%d",&h[i]);
bool lt=false,gt=false;
for(int i=1;i<=n/2;i++)//有一个结点只有一个左儿子
{
for(int j=0;j<2;j++)
{
if(2*i+j<=n){
if(h[2*i+j]>h[i]) lt=true;
else gt=true;}
}
}
if(gt&<) puts("Not Heap");
else if(gt) puts("Max Heap");
else if(lt) puts("Min Heap");
dfs(1);
puts("");
}
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla