проверка допустимости минимального массива кучи

У меня есть эта функция 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'

python min-heap
person Mango Lemon    schedule 30.01.2021    source источник
comment
None нельзя сравнивать с другими элементами, поэтому он не должен быть частью массива кучи. Я думаю, что полученное двоичное дерево не сбалансировано...   -  person Kate Melnykova    schedule 30.01.2021
comment
При использовании массива для реализации кучи корневой узел может иметь индекс 0 или 1, т.е. the-index-0-is-left-unused#:~:text=The%20string%20x%20gives%20the,%22take%20the%20right%20child%22.">Почему в куче, реализованной массивом, индекс 0 остается неиспользованным. Поскольку None находится в индексе 0, кажется, что корневой узел находится в индексе 1, поэтому массив следует проверить соответствующим образом.   -  person DarrylG    schedule 30.01.2021

Ответы (2)


arrow_upward
0
arrow_downward

Вместо того, чтобы сверять каждый нелистовой узел с его левым дочерним и правым дочерними узлами (если они есть), проще сверить каждый некорневой узел с его родителем.

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))
person kaya3    schedule 30.01.2021

arrow_upward
0
arrow_downward

Изменять

    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

to

    _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

Таким образом, он сначала удалит все None из списка, а только потом сделает сравнение.

person Programmer    schedule 30.01.2021
comment
Хммм, это все еще дает мне ошибку NoneTpe - person Mango Lemon; 30.01.2021
comment
@MangoLemon, тогда опубликуйте, пожалуйста, полную и точную трассировку, а не только часть последней строки. - person Programmer; 30.01.2021
comment
@MangoLemon я отредактировал свой ответ - person Programmer; 30.01.2021