A binary max heap is a rooted tree with integer labeled nodes such that:
- No node has more than 2 children.
- The label of every node is greater than all of its children.
We say a sequence of integers is heapable if there exists a binary max heap, whose labels are the sequence's elements, such that if \$p\$ is the parent of \$n\$, then the sequence has \$p\$ before \$n\$.
Alternatively, a sequence is heapable if there is a way to initialize a binary max heap whose root is its first element, and then insert the remaining elements one at a time in the order they appear in the sequence, while maintaining the binary max heap property.
[100, 19, 17, 36, 25, 3, 2, 1, 7]is heapable, with this heap showing why. In the heap,
19is the parent of
19comes in the sequence before
3does. This is true for any parent and child.
[100, 1, 2, 3]is not heapable. If the sequence was heapable, each parent must be both larger, and come before, any of its children. Thus, the only possible parent of
100. But this is impossible in a binary heap, as each parent has at most two children.
Given a non-empty array of distinct positive integers, determine if it is heapable.
This is code-golf so the goal is to minimize your source code as measured in bytes.
[4, 1, 3, 2] -> True [10, 4, 8, 6, 2] -> True [100, 19, 17, 36, 25, 3, 2, 1, 7] -> True [6, 2, 5, 1, 3, 4] -> True [100, 1, 2, 3] -> False [10, 2, 6, 4, 8] -> False [10, 8, 4, 1, 5, 7, 3, 2, 9, 6] -> False
The typical array representation of a heap is a heapable sequence, but not all heapable sequences are in this form (as the above examples show).
Most sources define heapable sequences with a min heap, rather than a max heap. It's not a big difference, but I imagine programmers are more familiar with max heaps than min heaps.
This is a decision-problem standard rules apply.