Функция минимальной кучи

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

Что я написал до сих пор:

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))

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

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


python heap min-heap
person Mat.S    schedule 07.04.2013    source источник

Ответы (1)


arrow_upward
2
arrow_downward

У вас есть три разных случая для данного 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
person poke    schedule 07.04.2013