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

Question

Я написал a min-max heap, то есть кучу, где поиск минимума и максимума - постоянные операции. Теперь я хочу создать тесты для своего класса, поэтому я решил реализовать функцию, которая проверяет, является ли куча 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 не существует.

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

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

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

Edit 1

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

Edit 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

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

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

EDIT: мин-макс кучи бинарное дерево, которое удовлетворяет два свойства:

1) Т имеет кучи-образную форму

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

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 

Answer 2

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

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

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