PAT(Advanced Level)A1147. Heaps

题意

判断给定的完全二叉树是否为堆

思路

• 完全二叉树用静态存储，注意是从index 1开始放
• 解决了怎么存储之后，接下来就是怎么判断堆的问题了❓
  • 看有没有破坏最大堆和最小堆的性质，破坏其中一个就是另一个，都破坏了说明根本不是堆，设置两个标志位
  • 也就是我们从第2个节点到最后，都反复检查当前节点和父节点的关系

代码

#include <iostream>
#include <vector>
#include <map>
using namespace std;
int max_heap, min_heap;
int trees, keys;
vector<int> path;
// 判断是否为堆，改变对应标志位
void judge(vector<int>& v) {
    for(int i = 2; i <= keys; i++) {
        if(v[i/2] > v[i])   min_heap = 0;   // 出现了父节点 > 孩子结点，不可能是最小堆
        if(v[i/2] < v[i])   max_heap = 0;   // 出现了父节点 < 孩子结点，不可能是最大堆
    }
}
// 后序遍历，用vector来存放结果
void post_travel(vector<int>& v, int index) {
    if(index <= keys) {
        post_travel(v, index * 2);
        post_travel(v, index * 2 + 1);
        path.emplace_back(v[index]);
    }
}
int main() {
    cin >> trees >> keys;
    vector<int> my_tree;
    for(int i = 0; i < trees; i++) {
        my_tree.clear();
        my_tree.resize(keys + 1);
        for(int j = 1; j <= keys; j++)   cin >> my_tree[j];
        max_heap = 1;
        min_heap = 1;
        judge(my_tree);
        path.clear();
        
        if(max_heap == 1 && min_heap == 0) {
            cout << "Max Heap
";
            post_travel(my_tree, 1);
            for(int i = 0; i < path.size() - 1; i++) {
                cout << path[i] << " ";
            }
            cout << path.back();
        }else if(max_heap == 0 && min_heap == 1) {
            cout << "Min Heap
";
            post_travel(my_tree, 1);
            for(int i = 0; i < path.size() - 1; i++) {
                cout << path[i] << " ";
            }
            cout << path.back();
        }else {
            cout << "Not Heap
";
            post_travel(my_tree, 1);
            for(int i = 0; i < path.size() - 1; i++) {
                cout << path[i] << " ";
            }
            cout << path.back();
        }
        if(i != trees - 1)  cout << endl;
    }
  	return 0;
}