A1147.md

A1147 Heaps

1. 题目理解

给出一棵完全二叉树的层序遍历，判断是不是堆，如果是，继续判断是大顶堆还是小顶堆。

（表面考堆，实际考完全二叉树）

2.题目分析

完全二叉树的层序遍历和其顺序存储是一致的，直接读入即可。判断堆时，可以离线建堆也可以在线判断。笔者采用的是建堆方法。

3.参考代码

#include <bits/stdc++.h>
using namespace std;

const int M = 128;
const int N = 1024;
int m, n;
// priority_queue<int, vector<int>, less<int>> MaxHeap;
// priority_queue<int, vector<int>, greater<int>> MinHeap;

void upAdjustMax(vector<int> &heap, int low, int high)
{
    int i = high, j = i / 2;
    while (j >= low)
        if (heap[j] < heap[i])
        {
            swap(heap[j], heap[i]);
            i = j;
            j = i / 2;
        }
        else
            break;
}

void upAdjustMin(vector<int> &heap, int low, int high)
{
    int i = high, j = i / 2;
    while (j >= low)
        if (heap[j] > heap[i])
        {
            swap(heap[j], heap[i]);
            i = j;
            j = i / 2;
        }
        else
            break;
}

int cnt = 0;
void postOrder(vector<int> v, int root, int n)
{
    if (root > n)
        return;
    postOrder(v, 2 * root, n);
    postOrder(v, 2 * root + 1, n);
    printf("%d", v[root]);
    if (++cnt < n)
        printf(" ");
    else
        printf("\n");
}

int main()
{
    int x;
    scanf("%d%d", &m, &n);
    vector<int> MaxHeap(n + 1);
    vector<int> MinHeap(n + 1);
    vector<int> test(n + 1);
    for (int i = 0; i < m; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            scanf("%d", &x);
            test[j] = x;
            MaxHeap[j] = x;
            MinHeap[j] = x;
            upAdjustMax(MaxHeap, 1, j);
            upAdjustMin(MinHeap, 1, j);
        }
        if (test == MaxHeap)
            printf("Max Heap\n");
        else if (test == MinHeap)
            printf("Min Heap\n");
        else
            printf("Not Heap\n");

        postOrder(test, 1, n);
        cnt = 0;
    }

    system("pause");
    return 0;
}

也可利用c++自带的heap一套实现：

#include<bits/stdc++.h>
using namespace std;

void post_order(vector<int> &tree, int root)
{
    int num = tree.size();
    if(root > num - 1)
        return;

    post_order(tree, 2 * root + 1);
    post_order(tree, 2 * root + 2);

    printf("%d", tree[root]);
    if(root == 0)
        printf("\n");
    else
        printf(" ");
}

int main()
{
    int m, n, x;

    scanf("%d%d", &m, &n);
    for(int i = 0; i < m; i++)
    {
        vector<int> vec;
        for(int j = 0; j < n; j++)
        {
            scanf("%d", &x);
            vec.push_back(x);
        }

        vector<int> max_heap = vec, min_heap = vec;
        make_heap(max_heap.begin(), max_heap.end());
        make_heap(min_heap.begin(), min_heap.end(), greater<int>());

        if(vec == max_heap)
            printf("Max Heap\n");
        else if(vec == min_heap)
            printf("Min Heap\n");
        else
            printf("Not Heap\n");

        post_order(vec, 0);
    }
    return 0;
}

或者还有更为精简的方法：

bool isMax(int root)
{
	if(root * 2 > n) 
        return true;
	else if(root * 2 == n) 
        return Heap[root] >= Heap[n];
	else 
        return Heap[root] >= max(Heap[root * 2], Heap[root * 2 + 1]) && isMax(root * 2) && isMax(root * 2 + 1);
}


bool isMin(int root)
{
	if(root * 2 > n) 
        return true;
	else if(root * 2 == n) 
        return Heap[root] <= Heap[n];
	else 
        return Heap[root] <= min(Heap[root * 2], Heap[root * 2 + 1]) && isMin(root * 2) && isMin(root * 2 + 1);
}

注意点：

• 用vector容器，方便直接==比较。
• 一定要记熟插入堆的调整方法。注意代码中传的是堆的引用。
• 每次调整的区间是当前最新插入的元素位置，而不是数组末尾！

（附上不建堆方法）

#include<bits/stdc++.h>
using namespace std;

const int N = 1024, M = 128;

void post_order(vector<int> &tree, int n, int root)
{
    if(root > n)
        return;

    post_order(tree, n, 2 * root);
    post_order(tree, n, 2 * root + 1);
    printf("%d", tree[root]);
    if(root != 1)
        printf(" ");
    else
        printf("\n");
}

int main()
{
    int n, m;
    scanf("%d%d", &m, &n);

    for(int i = 0; i < m; i++)
    {
        vector<int> tree(N);
        for(int j = 1; j <= n; j++)
            scanf("%d", &tree[j]);

        bool max_flag = true, min_flag = true;
        for(int j = 1; j <= n / 2; j++)
        {
            if(tree[j] > tree[2 * j])
                min_flag = false;
            if(tree[j] < tree[2 * j])
                max_flag = false;
                
            if(2 * j + 1 <= n) // 完全二叉树分支结点一定有左子树，右子树不一定
            {
                if(tree[j] > tree[2 * j + 1])
                    min_flag = false;
                if(tree[j] < tree[2 * j + 1])
                    max_flag = false;
            }
        }

        if(max_flag) printf("Max Heap\n");
        else if(min_flag) printf("Min Heap\n");
        else printf("Not Heap\n");

        post_order(tree, n, 1);
    }

    return 0;
}