检查最小堆数组是否有效

Question

我有这个函数 def validate(self) 应该检查给定数组是否是有效的最小堆。我认为它有效，但因为我的数组在开头有 None，如 [None、2、3、5]，它似乎运行出现问题并给我错误 '<' not supported between instances of 'int' and 'NoneType'

如何跳过代码中的 none 值？

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

新代码：

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

错误：

  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

改变

    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

至

    _items = list(filter(None, self._items)) # delete all Nones in the list, save the cleaned list into a local variable in case you want to use the unmodified list somewhere else
    for i in range(int((n - 2) / 2) + 2):
        if _items[2 * i + 1] < _items[i]: 
            return False

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

这样，它会先从列表中删除所有的Nones，然后才进行比较。

Answer 2

与其将每个非叶节点与其左子节点和右子节点（如果有的话）进行比较，不如将每个非根节点与其父节点进行比较。

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

您还可以使用 all:

的推导式

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

检查最小堆数组是否有效

checking if a min heap array is valid

python

min-heap