1147 Heaps (30 分)

(30)分水题~。

检查所有节点（除了根节点）和它的父节点的关系，判断是否破坏最大堆或者最小堆的性质。

const int N=1010;
int heap[N];
bool maxheap,minheap;
int n;

void dfs(int u,vector<int> &post)
{
    if(u > 1)
    {
        if(heap[u] > heap[u/2]) maxheap=false;
        if(heap[u] < heap[u/2]) minheap=false;
    }

    if(u*2 <= n) dfs(u*2,post);
    if(u*2+1 <= n) dfs(u*2+1,post);
    post.pb(heap[u]);

}

int main()
{
    int T;
    cin>>T>>n;
    while(T--)
    {
        for(int i=1;i<=n;i++) cin>>heap[i];

        maxheap=minheap=true;

        vector<int> post;
        dfs(1,post);

        if(maxheap) puts("Max Heap");
        else if(minheap) puts("Min Heap");
        else puts("Not Heap");

        for(int i=0;i<post.size();i++)
            if(i) cout<<' '<<post[i];
            else cout<<post[i];
        cout<<endl;
    }
    //system("pause");
    return 0;
}