为什么这段代码是正确的，而它显然应该运行进入无限循环？

Question

一段时间以来，我一直对这段代码有疑问。函数递归调用的位置似乎不对。

我尝试了运行代码，是的，它运行进入了无限循环。

// I DEFINE HEAP STRUCTURE AS :
struct heap_array
{
  int *array;  // heap implementation using arrays(note : heap is atype of a tree).

  int capacity;  // how much the heap can hold.
  int size;   //how much size is currently occupied.

void MaxHeapify(struct heap_array *h,int loc)  // note : loc is the location of element to be PERCOLATED DOWN.
{
  int left,right,max_loc=loc;
  left=left_loc_child(h,loc);
  right=right_loc_child(h,loc);

  if(left !=-1 && h->array[left]>h->array[loc])
  {
    max_loc=left;
  }

  if(right!=-1 && h->array[right]>h->array[max_loc])
  {
    max_loc=right;
  }

  if(max_loc!=loc)  //i.e. if changes were made:
  {
    //swap the element at max_loc and loc
    int temp=h->array[max_loc];
    h->array[max_loc]=h->array[loc];
    h->array[loc]=temp;


  }
    MaxHeapify(h,max_loc); // <-- i feel that this recursive call is misplaced. I have seen the exact same code in almost all the online videos and some books i referred to. ALSO I THINK THAT THE CALL SHOULD BE MADE WITHIN THE SCOPE OF condition if(max_loc!=loc).
    //if no changes made, end the func right there.
}

Answer 1

在您当前的实现中，您似乎没有停止递归的基本情况。

请记住 you need a base case in a recursive function（在本例中为您的 MaxHeapify 函数），它看起来并不存在。

Here is an example of MaxHeap 可以看看

// A recursive function to max heapify the given 
    // subtree. This function assumes that the left and 
    // right subtrees are already heapified, we only need 
    // to fix the root. 
    private void maxHeapify(int pos) 
    { 
        if (isLeaf(pos)) 
            return; 

        if (Heap[pos] < Heap[leftChild(pos)] ||  
            Heap[pos] < Heap[rightChild(pos)]) { 

            if (Heap[leftChild(pos)] > Heap[rightChild(pos)]) { 
                swap(pos, leftChild(pos)); 
                maxHeapify(leftChild(pos)); 
            } 
            else { 
                swap(pos, rightChild(pos)); 
                maxHeapify(rightChild(pos)); 
            } 
        } 
    }

在这里，您可以看到以下的基本情况：

    if (isLeaf(pos)) 
        return;

您需要为递归函数添加一个基本案例。

为什么这段代码是正确的，而它显然应该运行进入无限循环？

Why is this code correct while it should clearly run into an infinite loop?

binary-heap

为什么这段代码是正确的，而它显然应该 运行 进入无限循环？

Why is this code correct while it should clearly run into an infinite loop?

binary-heap

为什么这段代码是正确的，而它显然应该运行进入无限循环？