Функция Min Heap

Question

Я хочу написать функцию, которая сообщает мне, является ли данный список мини-кучей.

То, что я написал до сих пор:

def is_min_heap(L): 
    return _is_min_heap(L, 0) 

def _is_min_heap(L, i): 
    if 
     #base case 
    else: 
     return (L[i] < L[2*i+1] and _is_min_heap(L, 2*i+1)) and (L[i] < L[2*i+2] and _is_min_heap(L, 2*1+2)) 

Я не уверен, что базовый случай должен быть и мои рекурсивные вызовы правильно?

Также как вы можете контролировать, чтобы индексы не были в конечном итоге вне диапазона?

Answer 1

У вас есть три разных случая для заданного i: либо у вас есть двое детей, и в этом случае вам нужно проверить свойство кучи для обоих детей, а также рекурсивно проверить оба поддерева; или у вас есть только левые дети, и в этом случае вам просто нужно проверить это; или у вас нет детей, т. е. i - это лист, который всегда является действительной кучей.

Вы можете проверить наличие детей, проверив, находится ли его индекс в списке со списком.

def _is_min_heap(L, i): 
    l, r = 2 * i + 1, 2 * i + 2 

    if r < len(L): # has left and right children 
     if L[l] < L[i] or L[r] < L[i]: # heap property is violated 
      return False 

     # check both children trees 
     return _is_min_heap(L, l) and _is_min_heap(L, r) 
    elif l < len(L): # only has left children 
     if L[l] < L[i]: # heap property is violated 
      return False 

     # check left children tree 
     return _is_min_heap(L, l) 
    else: # has no children 
     return True