Is it a heapable sequence?

Question

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 code-golf 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 decision-problem standard rules apply.

Answer 1

Haskell, 100 bytes

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.

Answer 2

BQN, 35 bytes^SBCS

{⟨⟩: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
}

Answer 3

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

Answer 4

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[0] and len(r[i])<2:q+=[({**r,i:r[i]+[V[0]],V[0]:[]},V[1:])]
 return 0

Try it online!