Is it a max-heap?

Question

A heap, also known as a priority-queue, is an abstract data type. Conceptually, it's a binary tree where the children of every node are smaller than or equal to the node itself. (Assuming it's a max-heap.) When an element is pushed or popped, the heap rearranges itself so the the biggest element is the next to be popped. It can easily be implemented as a tree or as an array.

Your challenge, should you choose to accept it, is to determine if an array is a valid heap. An array is in heap form if every element's children are smaller than or equal to the element itself. Take the following array as an example:

[90, 15, 10, 7, 12, 2]

Really, this is a binary tree arranged in the form of an array. This is because every element has children. 90 has two children, 15 and 10.

       15, 10,
[(90),         7, 12, 2]

15 also has children, 7 and 12:

               7, 12,
[90, (15), 10,        2]

10 has children:

                      2
[90, 15, (10), 7, 12,  ]

and the next element would also be a child of 10, except that there isn't room. 7, 12 and 2 would all also have children if the array was long enough. Here is another example of a heap:

[16, 14, 10, 8, 7, 9, 3, 2, 4, 1]

And here is a visualization of the tree the previous array makes:

Just in case this isn't clear enough, here is the explicit formula to get the children of the i'th element

//0-indexing:
child1 = (i * 2) + 1
child2 = (i * 2) + 2

//1-indexing:
child1 = (i * 2)
child2 = (i * 2) + 1

You must take an non-empty array as input and output a truthy value if the array is in heap order, and a falsy value otherwise. This can be a 0-indexed heap, or a 1-indexed heap as long as you specify which format your program/function expects. You may assume that all arrays will only contain positive integers. You may not use any heap-builtins. This includes, but is not limited to

• Functions that determine if an array is in heap-form
• Functions that convert an array into a heap or into heap-form
• Functions that take an array as input and return a heap data-structure

You can use this python script to verify if an array is in heap-form or not (0 indexed):

def is_heap(l):
    for head in range(0, len(l)):
        c1, c2 = head * 2 + 1, head * 2 + 2
        if c1 < len(l) and l[head] < l[c1]:
            return False
        if c2 < len(l) and l[head] < l[c2]:
            return False

    return True

Test IO:

All of these inputs should return True:

[90, 15, 10, 7, 12, 2]
[93, 15, 87, 7, 15, 5]
[16, 14, 10, 8, 7, 9, 3, 2, 4, 1]
[10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
[100, 19, 36, 17, 3, 25, 1, 2, 7]
[5, 5, 5, 5, 5, 5, 5, 5]

And all of these inputs should return False:

[4, 5, 5, 5, 5, 5, 5, 5]
[90, 15, 10, 7, 12, 11]
[1, 2, 3, 4, 5]
[4, 8, 15, 16, 23, 42]
[2, 1, 3]

As usual, this is code-golf, so standard loopholes apply and the shortest answer in bytes wins!

Answer 1

Jelly, 11 9 5 bytes

x2:ḊṂ

4 bytes removed thanks to Dennis!

Try it here.

Explanation

x2          Duplicate each element.
:Ḋ          Each element divided by the input with the first element removed,
            as integer, so there is a 0 only if some element in the duplicated
            list is less than the corresponding element in the other.
            There are also elements left unchanged, but it doesn't matter as
            the input is all positive.
Ṃ           Minimum in the list.

Answer 2

JavaScript (ES6), 34 30 bytes

a=>!a.some((e,i)=>e>a[i-1>>1])

Edit: Fixing my code for the spec clarification cost 1 byte, so thanks to @edc65 for saving 4 bytes.

Answer 3

Haskell, 33 bytes

f(a:b)=and$zipWith(<=)b$a:b<*"xx"

or

and.(zipWith(<=).tail<*>(<*"xx"))

Answer 4

J, 24 bytes

*/@:<:]{~0}:@,<.@-:@i.@#

Explanation

*/@:<:]{~0}:@,<.@-:@i.@#  Input: s
                       #  Count of s
                    i.@   Create range [0, 1, ..., len(s)-1]
                 -:@      Halve each
              <.@         Floor each
         0   ,            Prepend a zero to it
          }:@             Remove the last value to get the parent indices of each
      ]                   Identity function to get s
       {~                 Take the values from s at the parent indices
    <:                    For each, 1 if it is less than or equal to its parent else 0
*/@:                      Reduce using multiplication and return

Answer 5

MATL, 13 12 bytes

ttf2/k)>~4L)

Try it online! Or verify all test cases.

An array is truthy if it is non-empty and all its entries are nonzero. Otherwise it's falsy. Here are some examples.

Explanation

t     % Take input implicitly. Duplicate
tf    % Duplicate and push indices of nonzero entries. This gives [1 2 ... n] where n
      % is input size
2/k   % Divide by 2 and round down
)     % Index into input. Gives array of parents, except for the first entry
>~    % True for entries of the input that don't exceed those in the array of parents
4L)   % Discard first entry

Answer 6

Python 2, 45 bytes

f=lambda l:l==[]or l[len(l)/2-1]/l.pop()*f(l)

Outputs 0 for Falsy, nonzero for Truthy.

Checks that the last element is less than or equal to its parent at index len(l)/2-1. Then, recurses to check that the same is True with the last element of the list removed, and so on until the list is empty.

---

48 bytes:

f=lambda l,i=1:l==l[:i]or l[~-i/2]/l[i]*f(l,i+1)

Checks that at each index i, the element is at most its parent at index (i-1)/2. The floor-division produces 0 if this is not the case.

Doing the base case as i/len(l)or gives the same length. I had tried zipping at first, but got longer code (57 bytes).

lambda l:all(map(lambda a,b,c:b<=a>=c,l,l[1::2],l[2::2]))

Answer 7

Retina, 51 bytes

\d+
$*
^(?!(1+ )*(1+) 1* ?(?<-1>1+ )*(?(1)(?!))1\2)

Try it online!

---

Takes a space-separated list of numbers as input. Outputs 1/0 for truthy/false

Answer 8

R, 97 88 82 bytes

Hopefully I've understood this correctly. Now to see if I can get rid of some more bytes. Ditched the rbind and put in an sapply and deal with 1-based vector properly.

Implemented as an unnamed function

function(Y)all(sapply(1:length(Y),function(X)Y[X]>=Y[X*2]&Y[X]>=Y[X*2+1]),na.rm=T)

With a few of the test cases

> f=
+ function(Y)all(sapply(1:length(Y),function(X)Y[X]>=Y[X*2]&Y[X]>=Y[X*2+1]),na.rm=T)
> f(c(90, 15, 10, 7, 12, 2))
[1] TRUE
> f(c(93, 15, 87, 7, 15, 5))
[1] TRUE
> f(c(10, 9, 8, 7, 6, 5, 4, 3, 2, 1))
[1] TRUE
> f(c(5, 5, 5, 5, 5, 5, 5, 5))
[1] TRUE
> f(c(4, 5, 5, 5, 5, 5, 5, 5))
[1] FALSE
> f(c(90, 15, 10, 7, 12, 11))
[1] FALSE
> f(c(4, 8, 15, 16, 23, 42))
[1] FALSE

Answer 9

CJam, 19 16 13 12 bytes

q~_:_\(;./:*

Golfed off 3 bytes thanks to Dennis.

Try it here.

Answer 10

Pyth, 8 bytes

.AgV.i+h

       hQ      first element of input
      +  Q     plus input
    .i    Q    interleaved with input
  gV       Q   vectorized greater-than-or-equal comparison with input
.A             check if all results are true

Try it online

Answer 11

C++14, 134 105 bytes

#define M(d) (2*i+d<c.size()&&(c[i]<c[2*i+d]||f(c,2*i+d)==0))
int f(auto&c,int i=0){return!(M(1)||M(2));}

Requires c to be a container supporting .operator[](int) and .size(), like std::vector<int>.

Ungolfed:

int f(auto& c, int i=0) {
    if (2*i+1<c.size() && c[i] < c[2*i+1]) return 0;
    if (2*i+2<c.size() && c[i] < c[2*i+2]) return 0;
    if (2*i+1<c.size() && (f(c,2*i+1) == 0)) return 0;
    if (2*i+2<c.size() && (f(c,2*i+2) == 0)) return 0;
    return 1;
}

Could be smaller if truthy=0 and falsy=1 would be allowed.

Answer 12

R, 72 bytes

A slightly different approach from the other R answer.

x=scan();all(diff(x[c(a<-1:(N<-sum(1|x)),a,a*2,a*2+1)],l=N*2)<1,na.rm=T)

Reads input from stdin, creates a vector of all of the comparison pairs, subtracts them from each other, and checks that the result is a negative number or zero.

Explanation

Read input from stdin:

x=scan();

Create our pairs. We create indices of 1...N (where N is the length of x) for the parent nodes. We take this twice as each parent has (maximally) two children. We also take the children, (1...N)*2 and (1...N)*2+1. For indices beyond the length of x, R returns NA, 'not available'. For input 90 15 10 7 12 2, this code gives us 90 15 10 7 12 2 90 15 10 7 12 2 15 7 2 NA NA NA 10 12 NA NA NA NA.

                  x[c(a<-1:(N<-sum(1|x)),a,a*2,a*2+1)]

In this vector of pairs, each element has its partner at a distance of N*2 away. For example, item 1's partner is located at position 12 (6*2). We use diff to calculate the difference between these pairs, specifying lag=N*2 to compare the items to their correct partners. Any operations on NA elements simply return NA.

             diff(x[c(a<-1:(N<-sum(1|x)),a,a*2,a*2+1)],l=N*2)

Finally, we check that all of these returned values are less than 1 (i.e. that the first number, the parent, was bigger than the second number, the child), excluding NA values from consideration.

         all(diff(x[c(a<-1:(N<-sum(1|x)),a,a*2,a*2+1)],l=N*2)<1,na.rm=T)

Answer 13

Actually, 16 bytes

This answer is largely based on jimmy23013's Jelly answer. Golfing suggestions welcome! Try it online!

;;2╟┬Σ1(tZ`i<`Mm

Ungolfing

         Implicit input a.
;;       Duplicate a twice.
2╟       Wrap two of the duplicates into a list.
┬        Transpose the duplicates.
Σ        Sum all of the columns to get a flat list like this:
           [a_0, a_0, a_1, a_1, ..., a_n, a_n]
         This gets the parent nodes of the heap.
1(t      Get a[1:] using the remaining duplicate of a.
         This is a list of the child nodes of the heap.
Z`i<`M   Check if every child node is less than its parent node.
m        Get the minimum. This returns 1 if a is a max-heap, else 0.
         Implicit return.