Можно ли найти наименьшее значение в максимальной куче рекурсивно, не обращая массив - PullRequest
Новая
       13

Можно ли найти наименьшее значение в максимальной куче рекурсивно, не обращая массив

0 голосов
/ 02 апреля 2020

Я пытаюсь найти наименьшее значение в максимальной куче (хранится в массиве) рекурсивно, не обращая массив. У меня есть некоторые проблемы при попытке определить рекурсивный случай. Как дать правильный индекс для рекурсивного вызова? (начальный индекс с 1 вместо 0) Если первый узел хранится в слоте i, то я знаю, что его левый и правый узлы хранятся в слоте 2 * i и 2 * i + 1 соответственно, а также их собственные левый и правый узлы. Как передать эту информацию рекурсивно?

псевдокод: 

smallest(size ,index_of_parent_node){
   i = size/2
   if (i == 0)
      return A[i]
   else 
      return min[smallest(size/2 , index_of_left_of_parent) , smallest(size/2, index_of_right_of_parent)]

1 Ответ

1 голос
/ 02 апреля 2020

У меня возникли проблемы при попытке определить рекурсивный случай. Как дать правильный индекс для рекурсивного вызова? (начальный индекс с 1 вместо 0) Если первый узел хранится в слоте i, то я знаю, что его левый и правый узлы хранятся в слоте 2 * i и 2 * i + 1 соответственно, а также их собственные левый и правый узлы. Как передать эту информацию рекурсивно?

Текущая реализация не работает, потому что она не будет смотреть на все конечные узлы. Минимальным элементом будет один из листовых узлов.

Если вы хотите сделать это рекурсивно, тогда вы можете начать с узла root в max-heap и получить минимум из двух его поддеревьев, как показано ниже - 

def getSmallestNumber (maxHeapArray , size):
    #assuming maxHeapArray has at least one element
    #and 1-based indexing
    return helper(maxHeapArray, size, 1)

def helper (maxHeapArray, size, currentIndex):
    if currentIndex >= size:
       return maxHeapArray[currentIndex]

    currentNumber = maxHeapArray[currentIndex]
    leftIndex     = 2 * currentIndex   
    rightIndex    = 2 * currentIndex + 1
    leftMin       = helper(maxHeapArray, size, leftIndex)
    rightMin      = helper(maxHeapArray, size, rightIndex)
    return min(currentNumber, leftMin, rightMin)

You также можно выполнить линейный обход полного массива или половины элементов. Сложность времени для получения минимальных элементов из max-heap

...