当前位置:网站首页>Traverse Heap PAT Class A 1155 Heap Path
Traverse Heap PAT Class A 1155 Heap Path
2022-08-02 17:04:00 【keyboard sonata】
In computer science, a heap is a specialized tree-based data structure with heap properties:
If P is the parent node of C, the weight of the P node in the large top heap is greater than or equal to the weight of the C node, and the weight of the P node in the small top heap is less than or equal to the C nodepoint weight.
A common implementation of a heap is a binary heap, which is implemented by a complete binary tree.
To be sure, in a big-top/small-top heap, any path from root to leaf must be in non-increasing/non-decreasing order.
Your task is to check every path in a given complete binary tree to see if it is a heap.
Input format
The first line contains the integer N, which represents the number of nodes in the tree.The second line contains N distinct integers representing the sequence of level-order traversal of the given complete binary tree.
Output format
For a given tree, first output all paths from root to leaf.Each path occupies one line, the numbers are separated by spaces, and there must be no extra spaces at the beginning and end of the line.
The paths must be output in the following order: For each node in the tree, the path in its right subtree must be output before the path in its left subtree.
The last line, if it is a large top heap, output Max Heap, if it is a small top heap, output Min Heap, if it is not a heap, output Not Heap.
Data Range
1Input Example 1:
8
98 72 86 60 65 12 23 50
Example output 1:
98 86 23
98 86 12
98 72 65
98 72 60 50
Max Heap
Input Sample 2:
8
8 38 25 58 52 82 70 60
Output Sample 2:
8 25 70
825 82
8 38 52
8 38 58 60
Min Heap
Input Example 3:
8
10 28 15 12 34 9 8 56
Sample output 3:
10 15 8
10 15 9
10 28 34
10 28 12 56
Not Heap
My solution:
#include using namespace std;const int N = 1010;int n;int a[N];bool lt, gt;vector path;void dfs(int u){path.push_back(a[u]);if(2 * u > n){cout << path[0];for(int i = 1; i < path. size(); i ++ ) {cout << ' ' << path[i];if(path[i] < path[i - 1]) gt = true;else if(path[i] > path[i - 1]) lt = true;}cout << endl;}if(2 * u + 1 <= n) dfs(2 * u + 1);if(2 * u <= n) dfs(2 * u);path.pop_back();}int main(){cin >> n;for(int i = 1; i <= n; i ++ ){cin >> a[i];}dfs(1);if(lt && gt) puts("Not Heap");else if(lt) puts("Min Heap");else puts("Max Heap");return 0;}
边栏推荐
猜你喜欢
随机推荐
【无标题】
The difference and connection between dist, pdist and pdist2 in MATLAB
【无标题】
2022-07-21 第六小组 瞒春 学习笔记
延时函数-定时器
lambda表达式、Stream接口及Optional类
为什么四个字节的float表示的范围比八个字节的long表示的范围要广
集成电路实践----D触发器
lammps学习(二)联合原子模型聚乙烯拉伸
2022-7-15 第五组 瞒春 学习笔记
MySQL 视图(详解)
Redis + Caffeine实现多级缓存
告别手摇织布机的AI时代
Impulse response invariant method and bilinear transformation method for IIR filter design
已解决ModuleNotFoundError: No module named‘ pip‘(重新安装pip的两种方式)
vite.config.ts introduces the `path` module Note!
2022-07-23 第六小组 瞒春 学习笔记
PAT甲级 1078 哈希
ELK日志分析系统
如何正确且快速的清楚C盘!!释放C盘空间内存保姆级教程