c中的Max heapify创建无限递归

Question

这是 max heapify 的程序，我怀疑这个算法，如果一个已经最大的堆被传递给这个函数 MAX_HEAPIFY 在这种情况下 largest 将等于 i 仅直接递归调用 MAX_HEAPIFY 将仅在该递归中执行将无限进行

i am assuming that array index is starting from 1 instead of zero

   MAX_HEAPIFY(A,i,heapsize){
    l=2i;
    r=2i+1;
    if(l<=heapsize&& A[l]>A[i])
      largest=l;
    else
      largest=i;
    if(r<=heapsize&&A[r]>A[largest])
      largest=r;
    if(largest!=i)
      swap(A[i],A[largest])
    MAX_HEAPIFY(A,largest)
   }

Answer 1

复制此算法时可能缩进有问题。但是如果你把 MAX_HEAPIFY(A,largest) 放在这个 if(largest!=i) 条件下，那么算法是正确的。请参阅下面的算法以获得更多说明：

MAX_HEAPIFY(A,i,heapsize){
    l=2i;
    r=2i+1;
    if(l<=heapsize&& A[l]>A[i])
      largest=l;
    else
      largest=i;
    if(r<=heapsize&&A[r]>A[largest])
      largest=r;
    if(largest!=i) {
      swap(A[i],A[largest])
      MAX_HEAPIFY(A,largest)
    }
}

c中的Max heapify创建无限递归

Max heapify in c creating infinite recursion

c

algorithm

heap

data-structures