PAT甲级1147 Heaps

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI0MDY2Nw_size_16_color_FFFFFF_t_70]  
**思路：**  
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;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI0MDY2Nw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200619192810985.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI0MDY2Nw==,size_16,color_FFFFFF,t_70