【未完成】7-10 关于堆的判断 (25 分)
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/shiliang97/article/details/98790049
7-10 关于堆的判断 (25 分)
将一系列给定数字顺序插入一个初始为空的小顶堆H[]。随后判断一系列相关命题是否为真。命题分下列几种：
x is the root：x是根结点；x and y are siblings：x和y是兄弟结点；x is the parent of y：x是y的父结点；x is a child of y：x是y的一个子结点。
输入格式：
每组测试第1行包含2个正整数N（≤ 1000）和M（≤ 20），分别是插入元素的个数、以及需要判断的命题数。下一行给出区间[−10000,10000]内的N个要被插入一个初始为空的小顶堆的整数。之后M行，每行给出一个命题。题目保证命题中的结点键值都是存在的。
输出格式：
对输入的每个命题，如果其为真，则在一行中输出T，否则输出F。
输入样例：
5 4
46 23 26 24 10
24 is the root
26 and 23 are siblings
46 is the parent of 23
23 is a child of 10输出样例：
F
T
F
T#include <bits/stdc++.h>
using namespace std;
int Find(int x,int *heap) {
for(int i=1; ; i++)
if(heap[i]==x)
return i;
}
bool siblings(int x,int y,int *heap) {
x=Find(x,heap);
y=Find(y,heap);
if(heap[x/2]==heap[y/2])
return true;
else
return false;
}
bool child(int x,int y,int *heap) {
x=Find(x,heap);
y=Find(y,heap);
if(x/2==y)
return true;
else
return false;
}
void print(bool f){
if(f)
cout<<'T'<<endl;
else
cout<<'F'<<endl;
}
int main() {
int n,m;
cin>>n>>m;
int heap[1005]= {-999999};
for(int i=1; i<=n; i++) {
int temp;
cin>>temp;
heap[i]=temp;
int j=i;
while(temp<heap[j/2]) {
swap(heap[j],heap[j/2]);
j/=2;
}
}
int x,y;
string str;
for(int i=0; i<m; i++) {
cin>>x>>str;
if(str=="and") {
cin>>y>>str>>str;
print(siblings(x,y,heap));
} else {
cin>>str;
if(str=="a") {
cin>>str>>str>>y;
print(child(x,y,heap));
} else {
cin>>str;
if(str=="root")
print(Find(x,heap)==1);
else {
cin>>str>>y;
print(child(y,x,heap));
}
}
}
}
return 0;
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2019-08-07 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录