天梯L2-012

将一系列给定数字顺序插入一个初始为空的小顶堆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（$\le$ 1000）和M（$\le$ 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

我去，，被题意搞死了，，原题中第一句话：将一系列给定数字顺序插入一个初始为空的小顶堆H[]。，，这个要求每次一个数往里插，，这样的话，先全部输入再建堆

就不行了（建堆过程中插数和先建好再调整出来的树是不一样的（虽然都是小顶堆）

顺便学习了一下c和c++中字符串和数值的转换（虽然也没派上用场），，附一篇博客，，自我感觉写的蛮好：http://www.cnblogs.com/hujunzheng/p/5042068.html

本题代码，，写的有点乱，orz，估计仅限本人能看懂。。。

#include <iostream>
#include <cstdio>
#include <cstring>using namespace std;int heap[1005];
char str[80];
int n,m;void siftup(int i)
{int tmp,flag=0;while(i!=1&&!flag){if(heap[i]<heap[i/2])swap(heap[i],heap[i/2]);elseflag=1;i/=2;}
}
/*
void siftdown(int i)
{int tmp,flag=0;while(i*2<=n&&!flag){if(heap[i]>heap[i*2])tmp=i*2;elsetmp=i;if(i*2+1<=n)//右节点单独判断{if(heap[tmp]>heap[i*2+1])tmp=i*2+1;}if(tmp!=i){swap(heap[tmp],heap[i]);i=tmp;}elseflag=1;}
}
*/
/*
void creat()
{int i;for(i=n/2; i>=1; i--)siftdown(i);
}
*/
/*
void creat2()
{int i;for(i=1;i<=n;i++){heap[i]=a[i];siftup(i);}
}
*/
int exchange()
{int i,sum=0;int flag=0;for(i=0; str[i]; i++){if(str[i]=='-')//注意负数flag=1;if(str[i]>='0'&&str[i]<='9'){while(str[i]>='0'&&str[i]<='9'){sum*=10;sum+=str[i]-'0';i++;}break;}}if(flag)sum=-sum;return sum;
}int location(int x)
{int i,tmp;for(i=1; i<=n; i++)if(heap[i]==x){tmp=i;break;}return tmp;
}int main()
{int i,flag,x,y;scanf("%d%d",&n,&m);for(i=1; i<=n; i++){scanf("%d",&heap[i]);siftup(i);}//creat();while(m--){flag=0;scanf("%d",&x);getchar();gets(str);if(str[3]==' '){y=exchange();int tmp=location(x);if(tmp&1){if(heap[tmp-1]==y)flag=1;elseflag=0;}else{if(heap[tmp+1]==y)flag=1;elseflag=0;}}else if(str[3]=='a'){y=exchange();int tmp=location(x);if(heap[tmp/2]==y)flag=1;elseflag=0;}else if(str[3]=='t'&&str[7]=='r'){if(heap[1]==x)flag=1;elseflag=0;}else if(str[3]=='t'&&str[7]=='p'){y=exchange();int tmp=location(y);if(heap[tmp/2]==x)flag=1;elseflag=0;}if(flag)printf("T\n");elseprintf("F\n");}return 0;
}