An array is a max-heap when every node is at least as large as each of its children, that is heap[i] >= heap[2*i+1] and heap[i] >= heap[2*i+2] whenever those indices exist. Note that this says nothing about the order of the array itself: a max-heap is not sorted.
Write first_violation(heap) returning the smallest index whose children break the property, or -1 if the array is a valid max-heap.
Examples
Input: heap = [9, 5, 6, 2, 1]
Output: -1
Input: heap = [9, 5, 6, 7, 1]
Output: 1
Explanation: node 1 holds 5 but its left child, index 3, holds 7.
Constraints
0 <= len(heap) <= 10**5, values are integers- Only the parent-child pairs matter; a node may be smaller than its uncle or its cousin.
Goals
- State the max-heap property as a check on every parent-child pair
- Scan an array as a tree without building one
- Report the first offender rather than a yes-or-no answer