Decide whether an array of numbers is laid out as a valid min-heap.
What to build
A check of the heap property on an array.
Requirements
- The array is a min-heap when no item is smaller than its parent.
- Print
yeswhen it is a min-heap. - Otherwise print
noand the smallest index whose item is smaller than its parent.
Input
The first line has n. The second line has the n numbers.
Output
yes, or no followed by a space and an index.
Constraints
1 ≤ n ≤ 100.
Example
Input:
6
1 5 2 6 7 3
Output:
yes
Why it works
In a heap stored from index 0, the parent of index i is at (i − 1) / 2. If every item is at least as large as its parent, then every parent is at most as large as its children, which is the heap property.
Examples
Example 1 · Input
6 1 5 2 6 7 3
Expected output
yes
Example 2 · Input
5 3 4 1 9 8
Expected output
no 2
Hints
Hint 1
The parent of index i is (i - 1) / 2.
Hint 2
Check every index from 1 upwards: its value must not be smaller than its parent's.
Hint 3
Stop at the first index that breaks the rule.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
int main(void) {
int n, a[100];
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
int bad = -1;
for (int i = 1; i < n && bad == -1; i++) {
if (a[i] < a[(i - 1) / 2]) bad = i;
}
if (bad == -1) printf("yes\n");
else printf("no %d\n", bad);
return 0;
}