problem
L2-012 关于堆的判断 (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
手写堆
给定一个长为n的序列，建立小顶堆。给出m个询问，判断根节点，兄弟节点，父节点，子节点关系。
solution
建堆：没写过堆，但是跟线段树一样是完全二叉树，可以用数组存储，子节点编号p<<1,p<<1|1，perfect。题目要求按顺序建堆，所以边插入边向上调整。（不能转为二叉树再向下调整）父子关系当且仅当2n或2n+1时，当x%2==0且x,y相邻时为兄弟
#include<bits/stdc++.h>
using namespace std
;
const int maxn
= 10010;
int n
, m
;
vector
<int>v
;
void update(int i
){
if(i
==1)return ;
while(i
!=1){
if(v
[i
]<v
[i
/2]){
swap(v
[i
],v
[i
/2]);
i
/= 2;
}else{
break;
}
}
}
void judge1(int x
){
if(v
[1]==x
)cout
<<"T\n";
else cout
<<"F\n";
}
void judge2(int x
, int y
){
int px
= 0, py
= 0;
for(int i
= 1; i
<= n
; i
++){
if(v
[i
]==x
)px
= i
;
if(v
[i
]==y
)py
= i
;
}
if(px
>py
)swap(px
,py
);
if(px
%2==0&&py
-px
==1)cout
<<"T\n";
else cout
<<"F\n";
}
void judge3(int x
, int y
){
int px
= 0, py
= 0;
for(int i
= 1; i
<= n
; i
++){
if(v
[i
]==x
)px
= i
;
if(v
[i
]==y
)py
= i
;
}
if(px
*2==py
||px
*2+1==py
)cout
<<"T\n";
else cout
<<"F\n";
}
void judge4(int x
, int y
){
int px
= 0, py
= 0;
for(int i
= 1; i
<= n
; i
++){
if(v
[i
]==x
)px
= i
;
if(v
[i
]==y
)py
= i
;
}
swap(px
,py
);
if(px
*2==py
||px
*2+1==py
)cout
<<"T\n";
else cout
<<"F\n";
}
int main(){
cin
>>n
>>m
;
v
.resize(n
+1);
for(int i
= 1; i
<= n
; i
++){
cin
>>v
[i
]; update(i
);
}
for(int i
= 1; i
<= m
; i
++){
int x
,y
;string z
;
cin
>>x
>>z
;
if(z
=="and"){
cin
>>y
>>z
>>z
;
judge2(x
,y
);
}else{
cin
>>z
;
if(z
=="a"){
cin
>>z
>>z
>>y
;
judge4(x
,y
);
}else{
cin
>>z
;
if(z
=="root"){
judge1(x
);
}else{
cin
>>z
>>y
;
judge3(x
,y
);
}
}
}
}
return 0;
}
