checking if a min heap array is valid

Question

I have this function def validate(self) which should check if a given array is a valid min heap. I think it works but because my arrays have None at the beginning like [None, 2, 3, 5] it seems to run into problems and give me the error '<' not supported between instances of 'int' and 'NoneType'

How can i skip over the none value in my code?

def validate(self):
    """
    Validates the heap. Returns True if the heap is a valid min-heap, and
    False otherwise.

    """

    n = self.__len__() 
    for i in range(int((n - 2) / 2) + 2):

        if self._items[2 * i + 1] < self._items[i]: 
            return False

        if (2 * i + 2 < n and self._items[2 * i + 2] > self._items[i]): 
            return False
    return True

New code:

def validate(self):
    """
    Validates the heap. Returns True if the heap is a valid min-heap, and
    False otherwise.

    """

    n = self.__len__() 
    for i in range(int((n - 2) / 2) + 2):
        if self._items[i] != None:
            if self._items[2 * i + 1] < self._items[i]: 
                return False

        if (2 * i + 2 < n and self._items[2 * i + 2] > self._items[i]): 
            return False

Error:

  File "<doctest __main__.MinHeap.validate[8]>", line 1, in <module>
    h.validate()
  File "x-wingide-python-shell://114699264/2", line 219, in validate
TypeError: '>' not supported between instances of 'int' and 'NoneType'

Answer 1

Rather than checking each non-leaf node against its left child and its right child (if it has one), it is simpler to check each non-root node against its parent.

def validate(self):
    n = len(self._items)
    for i in range(2, n):
        if self._items[i // 2] > self._items[i]: 
            return False
    return True

You can also use a comprehension with all:

def validate(self):
    n = len(self._items)
    return all(self._items(i // 2) <= self._items[i] for i in range(2, n))