PAT（甲级）2021年春季考试
7-3 Structure of Max-Heap (25 分) 最大堆
【题目描述】
In computer science, a max-heap is a specialized tree-based data structure that satisfies the heap property: if P is a parent node of C, then the key (the value) of P is greater than or equal to the key of C. A common implementation of a heap is the binary heap, in which the tree is a complete binary tree.
Your job is to first insert a given sequence of integers into an initially empty max-heap, then to judge if a given description of the resulting heap structure is correct or not. There are 5 different kinds of description statements:
x is the root
x and y are siblings
x is the parent of y
x is the left child of y
x is the right child of y
Input Specification:
Each input file contains one test case. For each case, the first line gives 2 positive integers: N (≤1,000), the number of keys to be inserted, and M (≤20), the number of statements to be judged. Then the next line contains N distinct integer keys in [−10 4,10 4] which are supposed to be inserted into an initially empty max-heap. Finally there are M lines of statements, each occupies a line.
Output Specification:
For each statement, print 1 if it is true, or 0 if not. All the answers must be print in one line, without any space.
Sample Input:
5 6
23 46 26 35 88
35 is the root
46 and 26 are siblings
88 is the parent of 46
35 is the left child of 26
35 is the right child of 46
-1 is the root
Sample Output:
011010
【解题思路】
按照输入，将数字逐个加入最大堆中，并对堆进行调整。完成建堆以后，用一个map存储各数字在堆中的位置（数组下标），以供后面查询。
下面输入每行字符串，这里处理比较巧妙，逐个单词输入，并不需要用到复杂的字符串处理。具体看代码实现，每部分加上了注释，代表是五种查询中的哪一种，然后通过map找到数字对应的数组下标，判断是否符合，输出结果即可。
【满分代码】
#include <iostream>
#include <cstdio>
#include <string>
#include <map>
#include <algorithm>
using namespace std;
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n,m,a,b,d[1005];
string x,y,z,s,t;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>d[i];
for(int j=i;j>1;j/=2)
{
if(d[j]>d[j/2])
swap(d[j],d[j/2]);
else
break;
}
}//建最大堆
map<int,int> pos;
for(int i=1;i<=n;i++)
pos[d[i]]=i;//记录各数字在堆中的位置
while(m--)
{
cin>>a>>x;
if(x=="and")//a和b是否为兄弟结点
{
cin>>b>>y>>z;
if(pos[a]==0||pos[b]==0||pos[a]==pos[b])//结点a或b不存在，或者a和b是同一个结点
{
cout<<"0";
continue;
}
if(pos[a]/2==pos[b]/2)
cout<<"1";
else
cout<<"0";
}
else//(x=="is")
{
cin>>y>>z;
if(z=="root")//a是否为根节点
{
if(pos[a]==1)
cout<<"1";
else
cout<<"0";
}
else if(z=="parent")//a是否为b的父亲结点
{
cin>>s>>b;
if(pos[a]==0||pos[b]==0)
{
cout<<"0";
continue;
}
if(pos[a]==pos[b]/2)
cout<<"1";
else
cout<<"0";
}
else if(z=="left")//a是否为b的左子结点
{
cin>>s>>t>>b;
if(pos[a]==0||pos[b]==0)
{
cout<<"0";
continue;
}
if(pos[a]==pos[b]*2)
cout<<"1";
else
cout<<"0";
}
else if(z=="right")//a是否为b的右子结点
{
cin>>s>>t>>b;
if(pos[a]==0||pos[b]==0)
{
cout<<"0";
continue;
}
if(pos[a]==pos[b]*2+1)
cout<<"1";
else
cout<<"0";
}
}
}
return 0;
}