A heap is a specialized tree data structure that satisfies the heap property:
Pis a parent node of
C, then the value of
Pis greater than or equal to (in a max-heap) or less than or equal to (in a min-heap) the value of C.
There are two main types of heaps:
- Max Heap: The value of the parent node should be larger than or equal to its child nodes.
- Min Heap: The value of the parent node should be smaller than or equal to its child nodes.
We’ll concentrate on the max-heap as most of the standard libraries implement a max-heap for priority queues. In a max-heap, the root of the tree is the largest element, while the leaves are the smallest. Yet, there is no particular order for the leaf nodes. So, the only guarantee is that the root node is the largest one and its child nodes are smaller than or equal to its value.
Note that the last row of the heap is always filled from left to right. So, the leftmost leaf is filled the first and the rightmost leaf is filled the last - as demonstrated in the picture above.
A heap can be implemented as an array, with the first element of the array representing the root node. As each node has only 2 child nodes, we can arrange the indexing as:
- The root element has an index of 1.
- The left and right children are located at
2i+1respectively for all the nodes.
- The parent node of an element at index
iis located at index
i // 2.
The heap above can be written in a list as:
# Just read every line in the picture and write the numbers side by side heap = [None, 8, 5, 7, 1, 1, 6, 3, 1] # Or to see it better visually heap = [None, # We skip the index  to have a simpler indexing 8, # Index  5, 7, # Indices [2, 3] 1, 1, 6, 3, # Indices [4, 5, 6, 7] 1] # Index 
Challenge: Check if the binary tree is a heap
Given a binary tree represented with an array of
nnumbers (with indexing described above), you are asked to check if it satisfies the max-heap properties.
The first line of the input contains a single integer
n(1 ≤ n ≤ 100 000).
The next line contains
nspace-separated integers () representing the values of the elements in the heap.
The program should print
Yesin case the input binary tree satisfies the max-heap property, and
8 8 5 7 1 1 6 3 1
7 8 5 7 1 9 6 3
Time limit: 1 seconds
Memory limit: 512 MB
Output limit: 1 MB