Is Min Heap Function

Question

I want to write a function that tells me whether a given list is a min heap.

What I have written so far:

def is_min_heap(L):
    return _is_min_heap(L, 0)

def _is_min_heap(L, i):
    if 
         #base case
    else:
        return (L[i] < L[2*i+1] and _is_min_heap(L, 2*i+1)) and (L[i] < L[2*i+2] and _is_min_heap(L, 2*1+2))

I am not sure what the base case should be and is my recursive calls correct?

Also how can you control that the indexes are not eventually out of range?

Answer 1

You have three different cases for a given i: Either you have two children, in which case you need to check the heap property for both children and also recursively check both subtrees; or you have just a left children, in which case you just have to check that one; or you have no children, i.e. i is a leaf, which is always a valid heap by itself.

You can check the existence of a children by checking if its index is still in range with the list.

def _is_min_heap(L, i):
    l, r = 2 * i + 1, 2 * i + 2

    if r < len(L): # has left and right children
        if L[l] < L[i] or L[r] < L[i]: # heap property is violated
            return False

        # check both children trees
        return _is_min_heap(L, l) and _is_min_heap(L, r)
    elif l < len(L): # only has left children
        if L[l] < L[i]: # heap property is violated
            return False

        # check left children tree
        return _is_min_heap(L, l)
    else: # has no children
        return True