In computer science, a heap is a specialized tree-based data structure that satisfies the heap property: if P is a parent node of C, then the key (the value) of P is either greater than or equal to (in a max heap) or less than or equal to (in a min heap) the key of C. A common implementation of a heap is the binary heap, in which the tree is a complete binary tree. (Quoted from Wikipedia at https://en.wikipedia.org/wiki...One thing for sure is that all the keys along any path from the root to a leaf in a max/min heap must be in non-increasing/non-decreasing order.Your job is to check every path in a given complete binary tree, in order to tell if it is a heap or not.Input Specification:Each input file contains one test case. For each case, the first line gives a positive integer N (1<N≤1,000), the number of keys in the tree. Then the next line contains N distinct integer keys (all in the range of int), which gives the level order traversal sequence of a complete binary tree.Output Specification:For each given tree, first print all the paths from the root to the leaves. Each path occupies a line, with all the numbers separated by a space, and no extra space at the beginning or the end of the line. The paths must be printed in the following order: for each node in the tree, all the paths in its right subtree must be printed before those in its left subtree.Finally print in a line Max Heap if it is a max heap, or Min Heap for a min heap, or Not Heap if it is not a heap at all.Sample Input 1:898 72 86 60 65 12 23 50Sample Output 1:98 86 2398 86 1298 72 6598 72 60 50Max HeapSample Input 2:88 38 25 58 52 82 70 60Sample Output 2:8 25 708 25 828 38 528 38 58 60Min HeapSample Input 3:810 28 15 12 34 9 8 56Sample Output 3:10 15 810 15 910 28 3410 28 12 56Not Heap题目重点信息提取：1.输入：positive integer N正整数， N distinct integer keys，N个互不相等 的整数 给出一颗完全二叉树 level order traversal sequence of a complete binary tree 提取重点翻译：level order 与 complete binary tree ，input一个完全二叉树的层序遍历序列 2.输出： 重点翻译：first print all the paths from the root to the leaves 先打印出所有从根结点到叶子结点的路径，all the paths in its right subtree must be printed before those in its left subtree，到右子树的路径要先于到左子树路径打印。 画图对应样例的输入输出也可以快速判断出来思路：深度遍历并打印出所有的路径（先右后左），用vector存储路径上的所有结点，通过push和pop回溯，维护路径，关于 index <= n ，由于是先右后左，需要对只有左叶子结点而无右叶子结点的点进行特判。#include <iostream>#include <stdio.h>#include <vector>using namespace std;int n,a[1001],isMaxHeap = 1,isMinHeap = 1;vector<int> v;void R_dfs(int index){ //从右至左的深度优先遍历 if(index * 2 > n && index * 2 + 1 > n){ if( index <= n){ //由于是先右后左，需要对只有左叶子结点而无右叶子结点的点进行特判 for(int i = 0; i < v.size(); i++) printf("%d%s",v[i], i != v.size()-1 ? " " : “\n”); } } else{ v.push_back(a[index *2 + 1]); //深度遍历右子树 R_dfs(index * 2 + 1); v.pop_back(); v.push_back(a[index * 2]); //深度优先遍历左子树 R_dfs(index * 2); v.pop_back(); }}int main(){ scanf("%d",&n); for(int i = 1; i <= n; i++){ //这里从i=1开始，方便后续对二叉树有无右子树进行判断 scanf("%d",&a[i]); } v.push_back(a[1]); R_dfs(1); for(int i = 2; i <= n; i++){ //判断大小顶堆 if(a[i/2] > a[i]) isMinHeap = 0; else if(a[i/2] < a[i]) isMaxHeap = 0; } if(isMinHeap == 1) printf("%s\n",“Min Heap”); else printf("%s\n",isMaxHeap == 1 ? “Max Heap” : “Not Heap”); return 0;}