将一系列给定数字顺序插入一个初始为空的小顶堆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。

输入样例：

1
2
3
4
5
6
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

输出样例：

1
2
3
4
F
T
F
T

思路

首先简单介绍一下堆。堆是一个用数组实现的完全二叉树，从叶子到根是有序的。将根结点最大的堆叫做最大堆或大根堆，根结点最小的堆叫做最小堆或小根堆。堆这里最主要的就是插入操作（建堆可以用插入代替）。

经常习惯数据从下标1开始存储，数据0设置一个极限值，当是小根堆堆时候就设置一个数据中不会出现的最小值，是大根堆堆时候就设置一个不会出现的最大值。这个位置可以称为哨兵。目的就是可以在插入函数的循环判断里面少写一点条件。

插入操作：首先将要插入的数据放到已存的数据的末尾的下一个位置。然后up，判断这个位置的数和他上面的位置（idx/2)的数是否有正确的大小关系，没有的话就swap，然后再和上面的比较，以此类推，如果有一个大小位置正确就走出循环。当到最后idx/2=0时，这个位置的数是一个极限值，走出循环。

此题的getIndex函数就是找到x在堆中对应的位置（数组的下标）。

由于是二叉树（且下标从1开始），左子树就是idx * 2，右子树就是idx * 2+1。idx/2就是父节点。由此可以写出来判断函数。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
//测试点1 和 3 错误：
//因为没有设置哨兵
#include <iostream>
using namespace std;
#define mini -99999999
struct Node
{
    int data[1001];
    int size;
    int capcity;
};

Node MinHeap;

int getIndex(int x)
{
    for (int i = 1; i <= MinHeap.size; ++i)
        if (MinHeap.data[i] == x)
            return i;
    return 0;
}
void insert(int x)
{
    int idx = ++MinHeap.size;
    MinHeap.data[idx]=x;
    for (; MinHeap.data[idx / 2] > x; idx /= 2)
        swap(MinHeap.data[idx/2],MinHeap.data[idx]);
}

bool check(int x,int y,int idx)
{
    if(idx==1) return MinHeap.data[1]==x;
    if(idx==2) return getIndex(x)/2==getIndex(y)/2;
    if(idx==3) return getIndex(x)==getIndex(y)/2;
    if(idx==4) return getIndex(x)/2==getIndex(y);
}

int main()
{
    //init
    MinHeap.capcity = 1000;//可以存放数据的最大数量
    MinHeap.data[0] = mini;

    int N, M;
    cin >> N >> M;
    for (int i = 0; i < N; ++i)
    {
        int cur;
        cin >> cur;
        insert(cur);
    }

    while (M--)
    {
        int x, y;
        cin >> x;
        string str;
        cin >> str;
        int flag = 0;
        if (str == "and")
        {
            cin >> y;
            flag = 2;
            cin >> str;
            cin >> str;
        }
        else
        {
            cin >> str;
            if (str == "a")
            {
                cin >> str;
                cin >> str;
                cin >> y;
                flag = 4;
            }
            else
            {
                cin >> str;
                if (str == "root")
                {
                    flag = 1;
                }
                else
                {
                    flag = 3;
                    cin >> str;
                    cin >> y;
                }
            }
        }
       
        if (check(x,y,flag))
            cout << "T\n";
        else
            cout << "F\n";
    }
}