Проверьте, является ли куча min-max кучей

Question

Я написал кучу min-max, то есть кучу, где нахождение минимума и максимума являются постоянными операциями. Теперь я хочу создать тесты для своего класса, поэтому я решил реализовать функцию, которая проверяет, является ли куча min-max-heap. Вот, но я не уверен, что это на 100% правильно.

def is_min_max_heap(h):
    if not isinstance(h, MinMaxHeap):
        return False
    if h.heap:
        for item in h.heap:
            if not isinstance(item, HeapNode):
                return False
        for i, item in reversed(list(enumerate(h.heap))):
            g = h.grandparent_index(i)
            if g is not None:
                if h.is_on_even_level(i):
                    if h.heap[g] > item:
                        return False
                else:
                    if h.heap[g] < item:
                        return False            
    return True     

Обратите внимание, что элементы этой кучи представлены классом HeapNodeи именно поэтому я проверяю, self.heap содержит только объекты этого класса. Четные уровни, например, 0, 2, 4 и т. Д. Минимум этой кучи находится в self.heap[0], Максимум max(self.heap[1], self.heap[2]) (при условии, что оба существуют). h.grandparent_index(i) возвращается None если дедушка узла в i не существует.

Идея моего алгоритма очень проста. Я начинаю снизу и проверяю, не нахожусь ли я на четном нечетном уровне. Если на четном уровне, то я должен убедиться, что элемент больше, чем его прародитель. Если я нахожусь на странном уровне, я должен убедиться, что он меньше, чем его дедушка и бабушка.

Мой алгоритм правильный? Я что-то упускаю? Если это правильно, предложения по его улучшению хорошо приняты.

В конце концов моя реализация может быть полезна для кого-то еще.

Редактировать 1

Я только что заметил, что моя функция проверяет, правильно ли расположены элементы на четном (и, соответственно, нечетном) уровнях, но не проверяет, найден ли максимальный элемент на self.heap[1] или же self.heap[2] и что минимальный элемент находится на self.heap[0],

Редактировать 2

Я добавляю новый обновленный код в соответствии с правкой 1 и ответом @goCards.

def is_min_max_heap(h) -> bool:
    """Returns `True` if `h` is a valid `MinMaxHeap` object. `False` otherwise."""
    if not isinstance(h, MinMaxHeap):
        return False

    if h.heap:
        for item in h.heap:
            if not isinstance(item, HeapNode):
                return False

        if h.size() == 1:
            return True

        if h.size() == 2:
            return max(h.heap) == h.heap[1] and min(h.heap) == h.heap[0]

        if h.size() >= 3:
            if (h.heap[0] != min(h.heap) or
                (h.heap[1] != max(h.heap) and
                 h.heap[2] != max(h.heap))):
                return False

        for i, item in reversed(list(enumerate(h.heap))):
            p = h.parent_index(i)

            if p != -1:
                if h.is_on_even_level(i):
                    if h.heap[p] < item:
                        return False
                else:
                    if h.heap[p] > item:
                        return False

            g = h.grandparent_index(i)
            if g != -1:
                if h.is_on_even_level(i):
                    if h.heap[g] > item:
                        return False
                else:
                    if h.heap[g] < item:
                        return False
    return True

Answer 1

Более простой способ - удалить элементы из кучи. Алгоритм будет примерно таким:

• поп мин-макс и хранить их в массиве
• повторяйте, пока у вас больше не будет элементов в куче
• проверьте, есть ли у массива характеристики, которые вы ожидаете.

Проверяя массив, который вы генерируете после извлечения всех элементов в куче, вы должны иметь четные индексы, которые должны строго увеличиваться, и нечетные индексы, строго уменьшающиеся. Если это не так, ваша реализация кучи неверна.

Answer 2

В вашем алгоритме отсутствуют некоторые проверки. Рассмотрим приведенный ниже пример, который не является кучей минимальных и максимальных значений, но проходит ваш тест. Рассмотрим 5 как корень. Корень имеет другую ветку, но он не показан для простоты.

Используя ваш алгоритм, куча ниже объявлена ​​как куча min-max, но она не удовлетворяет свойствам кучи min-max. Ваш алгоритм должен также проверить родительский узел.

РЕДАКТИРОВАТЬ: Мин-макс куча представляет собой двоичное дерево, которое удовлетворяет двум свойствам:

1) Т имеет форму кучи

2) T - упорядоченный минимум-максимум: значения, хранящиеся в узлах на четных (нечетных) уровнях, меньше (больше) или равны значениям, хранящимся у их потомков (если они есть), где корень находится на нулевом уровне.

for i, item in reversed(list(enumerate(h.heap))):
    g = h.grandparent_index(i)
    p = h.parent_index(i)
    if g is not None and p is not None:
        if h.is_on_even_level(i):
            if item > h.heap[g]: pass #grandparent should be smallest in its subtree
            else: return False
            if item < h.heap[p]: pass #parent should be greatest in its subtree
            else: return False
        else: #odd level
            if item < h.heap[g]: pass #grandparent should be greatest in its subtree
            else: return False
            if item > h.heap[p]: pass #parent should be smallest in its subtree
            else: return False