A heap is a specialized tree data structure that satisfies the heap property:
🗼
If P is a parent node of C, then the value of P is greater than or equal to (in a max-heap) or less than or equal to (in a min-heap) the value of C.
An example of a max-heap with 8 nodes
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.
Implementation
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 and 2i+1 respectively for all the nodes.
The parent node of an element at index i is 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 [0] to have a simpler indexing
8, # Index [1]
5, 7, # Indices [2, 3]
1, 1, 6, 3, # Indices [4, 5, 6, 7]
1] # Index [8]
Challenge: Check if the binary tree is a heap
Given a binary tree represented with an array of n numbers (with indexing described above), you are asked to check if it satisfies the max-heap properties.
Input
The first line of the input contains a single integer n (1 ≤ n ≤ 100 000).
The next line contains n space-separated integers () representing the values of the elements in the heap.
Output
The program should print Yes in case the input binary tree satisfies the max-heap property, and No otherwise.
Examples
Input
Output
8
8 5 7 1 1 6 3 1
Yes
7
8 5 7 1 9 6 3
No
Explanation
Example 1
All the parent nodes have a value larger than or equal to their child nodes. Therefore, the heap property is satisfied.
Example 2
The node with a value of 9 is larger than its parent node. Therefore, the heap property is not satisfied.
