A27923. 是不是堆二叉堆可以用一棵完全二叉树来实现，但完全二叉树不一定满足堆的性质。本题就请你判断一棵给定的完全二叉树是不是堆。输入输入在一行中给出两个正整数：m（≤ 100）是将要测试的完全二叉树的数量；n（1 < n ≤ 1000）是完全二叉树中的结点数。 随后 m 行，每行给出 n 个互不相同的键值（均在整型范围内），为完全二叉树的层序遍历序列。输出对输入的每棵完全二叉树，如果它是最大堆（大顶堆），…
填空题
困难
知识点
题目描述
是不是堆
二叉堆可以用一棵完全二叉树来实现，但完全二叉树不一定满足堆的性质。本题就请你判断一棵给定的完全二叉树是不是堆。
输入
输入在一行中给出两个正整数：m（≤ 100）是将要测试的完全二叉树的数量；n（1 < n ≤ 1000）是完全二叉树中的结点数。 随后 m 行，每行给出 n 个互不相同的键值（均在整型范围内），为完全二叉树的层序遍历序列。
输出
对输入的每棵完全二叉树，如果它是最大堆（大顶堆），就在一行中输出 `Max Heap`；如果是最小堆（小顶堆），则输出 `Min Heap`；如果根本不是堆，则输出 `Not Heap`。然后在下一行输出这棵树的后序遍历序列。同行数字间以 1 个空格分隔，行首尾不得有多余空格。
样例输入
3 8
98 72 86 60 65 12 23 50
8 38 25 58 52 82 70 60
10 28 15 12 34 9 8 56样例输出
Max Heap
50 60 65 72 12 23 86 98
Min Heap
60 58 52 38 82 70 25 8
Not Heap
56 12 34 28 9 8 15 10参考答案
//参考代码1
#include <iostream>
#include <vector>
using namespace std;
string checkHeap(const vector<int>& tree) {
int n = tree.size();
for (int i = 0; i < n; ++i) {
int l = 2 * i + 1, r = 2 * i + 2;
if (l < n && tree[i] > tree[l]) return "Min Heap";
if (r < n && tree[i] > tree[r]) return "Min Heap";
if (l < n && tree[i] < tree[l]) return "Max Heap";
if (r < n && tree[i] < tree[r]) return "Max Heap";
}
return "Not Heap";
}
void printPostOrder(const vector<int>& tree, int i, vector<int>& res) {
if (i >= tree.size()) return;
printPostOrder(tree, 2 * i + 1, res);
printPostOrder(tree, 2 * i + 2, res);
res.push_back(tree[i]);
}
int main() {
int m, n;
cin >> m >> n;
while (m--) {
vector<int> tree(n);
for (int &x : tree) cin >> x;
cout << checkHeap(tree) << endl;
vector<int> res;
printPostOrder(tree, 0, res);
for (int i = 0; i < res.size(); ++i) cout << res[i] << (i == res.size() - 1 ? '\n' : ' ');
}
}
上一题
下一题