是否有可能在不反转数组的情况下递归地找到最大堆中的最小值

Question

我试图递归地在最大堆（存储在数组中）中找到最小值，而不反转数组。我在尝试定义递归情况时遇到一些问题。如何为递归调用提供正确的索引？ （从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)]

Answer 1

I have some problems trying to define the recursive case. How do I give the correct index to the recursive call? (starting index from 1 instead of 0)If the first node is stored in slot i, then I know that its left and right nodes are stored in slot 2*i and 2*i+1 respectively and so are their own left and right nodes. How do I pass this information recursively?

当前实现不起作用，因为它不会查看所有叶子节点。最小元素将是叶节点之一。

如果要递归地进行操作，则可以从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)

您还可以对整个数组或元素的一半进行线性遍历。 Time complexity to get min elements from max-heap