13
\$\begingroup\$

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.

\$\endgroup\$
1

4 Answers 4

5
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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
}
\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
0
0
\$\begingroup\$

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!

\$\endgroup\$
1
  • \$\begingroup\$ 154 \$\endgroup\$
    – Steffan
    Jun 20 at 15:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.