PAT（甲級）2021年春季考試 7-3 Structure of Max-Heap (25 分) 最大堆

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;
}