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?Answer1:
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