9-11-堆 关于堆的判断（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），分别是插入元素的个数、以及需要判断的命题数。下一行给出区间[内的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; const int MAXN=1005; const int inf=1e9; int n,m,k; int a[MAXN]; string s; int find_pos(int x) { for(int i=1; i<=n; ++i) { if(a[i]==x)return i; } return -1; } int main() { scanf("%d%d",&n,&m); for(int i=1; i<=n; ++i) { scanf("%d",&a[i]); int k=i; while(k>1&&a[k]<a[k/2]) { swap(a[k],a[k/2]); k=k/2; } } int x1,x2; while(m--) { scanf("%d",&x1); cin>>s; if(s=="and") { scanf("%d",&x2); cin>>s; cin>>s; if(find_pos(x1)/2==find_pos(x2)/2)puts("T"); else puts("F"); } else { cin>>s; if(s=="a") { cin>>s; cin>>s; scanf("%d",&x2); int pos1=find_pos(x1); int pos2=find_pos(x2); if(pos1/2==pos2)puts("T"); else puts("F"); } else { cin>>s; if(s=="root") { if(a[1]==x1)puts("T"); else puts("F"); } else { cin>>s; scanf("%d",&x2); int pos1=find_pos(x1); int pos2=find_pos(x2); if(pos2/2==pos1)puts("T"); else puts("F"); } } } } return 0; }

转载于:https://www.cnblogs.com/linguiquan/p/9050007.html