L2-012关于堆的判断
建堆的方式一般有两种 ：
1. 向上调整，适用于边插入边调整，即如果题目的建堆是动态的，流式数据，如本题就是流式数据，时间复杂度是nlogn2. 向下调整，适用于一次性给出N个数再建堆，即题目给的数据是批量的，时间复杂度是n。尤其要注意到题目建堆的过程是动态还是静态的，本题很明显地给出了动态建堆，“顺序”；还要注意，如果全部放进数组后再向上调整也可以，只不过本质上与向下调整一样，时间复杂度还是nlogn。边插入边调整只能用向上调整，因为数是从数组尾部插入的，它只能感知到父节点。本题要求建小根堆，即对于每一个节点来说，它的子节点都比他大，根节点最小。这题建堆倒不是很难，难的是后面居然还有一个字符串处理o(╥﹏╥)o字符串部分看代码吧整体算比较简单，综合性较强###ac✅️代码
```cpp
#include <iostream>
#include <algorithm>
#include <map>
#include <string>using namespace std;const int N = 1005;
int h[N], n, m;
map<int, int> pos;// 向上调整：满足题目“逐个插入”的要求
void up(int u)
{while (u / 2 >= 1 && h[u / 2] > h[u]) {swap(h[u / 2], h[u]);u /= 2;}
}int main()
{// 开启加速后，严禁混用 scanf/printfios::sync_with_stdio(false);cin.tie(0);if (!(cin >> n >> m)) return 0;// 逐个插入建堆for (int i = 1; i <= n; i++) {cin >> h[i];up(i);}// 记录每个节点值对应的下标for (int i = 1; i <= n; i++) {pos[h[i]] = i;}while (m--) {int a, b;string s;cin >> a >> s;if (s == "and") // 格式：a and b are siblings{cin >> b >> s >> s;if (pos[a] / 2 == pos[b] / 2 && pos[a] != pos[b]) cout << "T" << endl;else cout << "F" << endl;} else // 格式：a is ...{cin >> s >> s; // 读掉 "is" 和 "the"if (s == "root") // a is the root{cout << (pos[a] == 1 ? "T" : "F") << endl;} else if (s == "parent") // a is the parent of b{cin >> s >> b;cout << (pos[b] / 2 == pos[a] ? "T" : "F") << endl;}
else if (s == "child") // a is the child of b
{cin >> s >> b;cout << (pos[a] / 2 == pos[b] ? "T" : "F") << endl;
}}}return 0;
}