L2-012. 关于堆的判断-白红宇

L2-012. 关于堆的判断

阅读量：4114 次

发布时间：2019-05-25

本文共 1421 字，大约阅读时间需要 4 分钟。

将一系列给定数字顺序插入一个初始为空的小顶堆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 446 23 26 24 1024 is the root26 and 23 are siblings46 is the parent of 2323 is a child of 10

输出样例：

FTFT

思路：边输入边建堆，建堆的时候对堆进行调整，调整的时候只需要与他的父节点进行比较，一直把当前的这个结点调到他合适的位置，因为结点的范围是[-10000, 10000]，所以后面用map把节点的值和位置进行对应一下，在后面判断关系的时候直接用节点值的位置进行判断。由小顶堆的性质可知下面的判断方法是正确的；

1.如果该节点是父亲节点，则该节点的下标为1

2.如果两个结点是兄弟，那么他们的父亲节点一定一样

3.父节点的下标是子节点的1/2；

在输入关系的时候可以把一句话每次判断在分别输入每句话的信息，这样就可以把整数和字符串分开。

#include
   
    #include
    
     #include
     
      #include
      
       #include
       using namespace std;const int maxn=1050;int a[maxn];int n,m,cnt;//int idx[maxn];map
        
          idx;void Build(int id){ int val=a[id]; int pos=id; while(pos>1&&val
         
          >n>>m; for(int i=0; i
          
           >x; charu(x); } for(int i=1; i<=cnt; i++) { idx[a[i]]=i; } for(int ka=0; ka
           
            >x; string s; cin>>s; if(s[0]=='a') { string ss,sss; int y; cin>>y; cin>>ss>>sss; int rx=idx[x]; int ry=idx[y]; if(rx/2==ry/2) cout<<"T"<
            
             >ss; if(ss[0]=='a') { string s1,s2; cin>>s1>>s2; int y; cin>>y; int rx=idx[x]; int ry=idx[y]; if(rx/2==ry) cout<<"T"<
             
              >s1; if(s1[0]=='r') { int rx=idx[x]; if(rx==1) cout<<"T"<
              
               >s2; int y; cin>>y;// cout<
               
                <

转载地址：http://gfgsi.baihongyu.com/

你可能感兴趣的文章