PTA-关于堆的判断(25分)

 

一、堆的概念:

  堆是完全二叉树。参考:(4条消息) 数据结构堆的概念&&堆排序的思想以及算法过程详解(图文)_LifeGoesOn-CSDN博客_堆的概念

  

 二、堆的初始化:

  一般给出一个数组,需要一个一个数的添加到堆,而堆也分为大顶堆和小顶堆,此时需要了解堆的上调和下调。

参考:https://blog.csdn.net/caipengbenren/article/details/86680768

 

 二、例题:

L2-012 关于堆的判断 (25 分)  

将一系列给定数字顺序插入一个初始为空的小顶堆H[]。随后判断一系列相关命题是否为真。命题分下列几种:

  • x is the rootx是根结点;
  • x and y are siblingsxy是兄弟结点;
  • x is the parent of yxy的父结点;
  • x is a child of yxy的一个子结点。

输入格式:

每组测试第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
    作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB  
  C++ (g++)   代码:
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
using namespace std;

vector<int> heap;
int Index[20010] ={0};

//上调,成为小顶堆
void siftup(int i){
    if(i==1) return;
    int flag = 0;
    while(i!=1&&flag==0){
        if(heap[i]<heap[i/2])
            swap(heap[i],heap[i/2]);
        else
            flag=1;
        i/=2;
    }
}

int main(){
    int n,m;
    cin>>n>>m;
    heap.resize(n+1);//让索引从1开始
    for(int i=1;i<=n;i++){
        cin>>heap[i];
        siftup(i);
    }
    //存索引
    for(int i=1;i<=n;i++){
        Index[heap[i]+10000]=i;
    }
    string s1;//第一个字符串,is或者and
    for(int i=0;i<m;i++){
        int firstNum;
        cin>>firstNum;
        cin>>s1;
        if(s1[0]=='a'){ //and ....
            int secondNum;
            cin>>secondNum;
            string s;//are siblings
            getline(cin,s);
            if(Index[firstNum+10000]/2 == Index[secondNum+10000]/2)
                cout<<"T"<<endl;
            else
                cout<<"F"<<endl;
        }else{  // is...
//             string s2; // a 或者  the
            cin>>s1;
            if(s1[0]=='a'){
                string s3,s4;  //  child  和  of
                cin>>s3>>s4;
                int num;  //"23 is a child of 10" 的最后一个数
                cin>>num;
                if(Index[firstNum+10000]/2 == Index[num+10000])
                    cout<<"T"<<endl;
                else
                    cout<<"F"<<endl;
            }else{  //the root 或者 the parent
                string s5; //root 或者 parent
                cin>>s5;
                if(s5=="root"){
                    if(Index[firstNum+10000]==1)
                        cout<<"T"<<endl;
                    else
                        cout<<"F"<<endl;
                }else{
                    string s6;
                    cin>>s6;
                    int num1;
                    cin>>num1;
                    if(Index[firstNum+10000]==Index[num1+10000]/2)
                        cout<<"T"<<endl;
                    else
                        cout<<"F"<<endl;
                }
            }
        }
    }
}

 

 

 

上一篇:1060 爱丁顿数 (25 分)


下一篇:抢红包 (25 分)