PAT甲级1147 Heaps-蒲公英云

PAT甲级1147 Heaps

冷不防 2023-02-19 09:24 219阅读 0赞

在这里插入图片描述
思路：
1.判断堆的类型通过按层序遍历顺序遍历一遍这棵树，如果子树结点值大于根，则maxheap置为false；类似的，如果子树结点值小于根，则minheap置为false
最后根据minheap和maxheap的值输出相应结果
2.后序遍历就是常规的方法，不同在于堆结构在数组中实现，根据下标遍历

代码

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
vector<int> v,sequence;
bool maxheap=true,minheap=true;
void judge(int low,int high)
{ 
    queue<int> q;
    q.push(low);
    while(!q.empty())
    { 
        int qq=q.front();
        q.pop();
        //if(!minheap&&!maxheap)break;
        if(qq*2<=high)
        { 
            q.push(qq*2);
            if(v[qq*2]<v[qq])minheap=false;
            if(v[qq*2]>v[qq])maxheap=false;
        }
        if(qq*2+1<=high)
        { 
            q.push(qq*2+1);
            if(v[qq*2+1]<v[low])minheap=false;
            if(v[qq*2+1]>v[low])maxheap=false;
        }
    }
}
void post(int index,int high)//后序遍历
{ 
    if(index*2<=high)post(index*2,high);
    if(index*2+1<=high)post(index*2+1,high);
    sequence.push_back(v[index]);
    return;
}
int main()
{ 
    int m,n;
    cin>>m>>n;
    v.resize(n+5);
    while(m--)
    { 
        for(int i=1;i<=n;i++)cin>>v[i];
        maxheap=minheap=true;
        judge(1,n);
        if(maxheap)cout<<"Max Heap"<<endl;
        else if(minheap)cout<<"Min Heap"<<endl;
        else cout<<"Not Heap"<<endl;
        sequence.clear();
        post(1,n);
        for(int i=0;i<sequence.size();i++)
        { 
            if(i!=sequence.size()-1)cout<<sequence[i]<<" ";
            else cout<<sequence[i]<<endl;
        }
    }
    return 0;
}