題目?jī)?nèi)容

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/Heap_(data_structure))

Your job is to tell if a given complete binary tree is a heap.

Input Specification:

Each input file contains one test case. For each case, the first line gives two positive integers: M (?100), the number of trees to be tested; and N (1<N?1,000), the number of keys in each tree, respectively. Then M lines follow, each 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, 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. Then in the next line print the tree's postorder traversal sequence. All the numbers are separated by a space, and there must no extra space at the beginning or the end of the line.

Sample Input:

Sample Output:

題目要點(diǎn)

本題 30 分，考察的是堆的判定，并輸出堆的后序遍歷序列。

處理堆的問(wèn)題時(shí)，首先要利用堆本身是完全二叉樹(shù)的性質(zhì)迅速定位左右孩子節(jié)點(diǎn)。根節(jié)點(diǎn)要從下標(biāo)1開(kāi)始存儲(chǔ)，對(duì)于任意節(jié)點(diǎn)root來(lái)說(shuō)，其左孩子下標(biāo)為2*root，右孩子下標(biāo)為2*root+1，父親下標(biāo)為root//2（向下取整）。有了這些結(jié)論就可以通過(guò)遍歷各個(gè)節(jié)點(diǎn)判斷是否符合堆的性質(zhì)。

如果完全二叉樹(shù)的所有孩子節(jié)點(diǎn)都比其父親節(jié)點(diǎn)小，那么這就是一個(gè)最大堆；反之，所有孩子節(jié)點(diǎn)都比父親節(jié)點(diǎn)大是最小堆。如果既不是最小堆、又不是最大堆，那么該完全二叉樹(shù)就不是堆。

源代碼