# Is it a heapable sequence?

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.

For example:

• The sequence [100, 19, 17, 36, 25, 3, 2, 1, 7] is heapable, with this heap showing why. In the heap, 19 is the parent of 3, and 19 comes in the sequence before 3 does. This is true for any parent and child.

• The sequence [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 1, 2, and 3 is 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 so the goal is to minimize your source code as measured in bytes.

## Test cases

[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


Notes:

• 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 standard rules apply.

• Jun 18, 2022 at 6:38

x!(q@(n,y):z)=[(2,x):(n-1,y):z|y>x,n>0]++map(q:)(x!z)
x!_=[]
g(x:y)=[]<foldl((.(!)).(>>=))[[(2,x)]]y


Try it online!

## Explanation

We look for a heap using breadth first search. We keep track of the nodes and the number of available children in a list. We discard any nodes that already have two children. They are just not necessary any more since we only care about if there is a solution, not what it is.

At each step we attempt to insert a value at every location allowing it if we find a node with available children and a value greater than the value we are inserting.

If we manage to find a way to insert every value then we return True otherwise False.

# BQN, 35 bytesSBCS

{⟨⟩:1;×⊑⍒𝕩?0;∨´∧´¨𝕊¨¨⊔⟜v¨⥊↕2¨v←1↓𝕩}


Run online!

Commented

{
⟨⟩:1   ;  # The empty sequence is heapable
×⊑⍒𝕩?0 ;  # Not heapable if the maximum is not at index 0
v←1↓𝕩     # Now consider the sequence without the first value
∨´        # It is heapable if any ...
⊔⟜v¨⥊↕2¨v #   ... way of splitting it
∧´¨𝕊¨¨    #   ... results in two heapable subsequences
}


# JavaScript (ES7), 81 bytes

Returns $$\0\$$ or $$\1\$$.

f=([v,...a],t=[2**32-3])=>!v|t.some((x,i)=>x/4>v&x%4<2&&f(a,b=[...t,v*4],b[i]++))


Try it online!

### How?

We don't really need to keep track of the exact structure of the binary tree. In particular, we don't need to 'remember' the parent of a given node as long as we are sure that it was a valid connection when we added it.

We store the tree as a list of integers where the 2 least significant bits represent the number of child nodes and the higher bits represent the value of the node.

For instance a $$\6\$$ with 1 child node is stored as $$\25\$$:

11001
\_/\/
|  \_ 1 child node
+---- value = 6


We do a recursive search, looking for all valid parents for a given value. For each valid connection, we update the parent and simply add the child at the end of the list.

The list is initialized with a pseudo node whose value is $$\2^{32}-3\$$ so that the root node can be attached to it:

11111111111111111111111111111101
\____________________________/\/
|                \_ 1 child
+------------------ max. possible value with
this encoding scheme


# Python3, 170 bytes:

def f(v):
q=[({v.pop(0):[]},v)]
while q:
r,V=q.pop(0)
if[]==V:return 1
for i in r:
if i>V and len(r[i])<2:q+=[({**r,i:r[i]+[V],V:[]},V[1:])]
return 0


Try it online!

• 154 Jun 20, 2022 at 15:35