algorithm - MIN_HEAPIFY 算法

Question

以下 MIN_HEAPIFY 算法是否正确？

MIN_HEAPIFY(A,i)
{
l=LEFT(i);//calculates the left childs location
r=RIGHT(i);//right childs location

if((l<=A.heap_size)AND(A[l]<A[i]))
   small=l;
else
   small=i;

if((r<=A.heapsize)&&(A[small]>A[r]))
   small=r;

if(small!=i)
  {
   exchange A[i] with A[small];
   MIN_HEAPIFY(A,i)
  }
}

Answer 1

不，这不正确，

if(small!=i)
  {
   exchange A[i] with A[small];
   MIN_HEAPIFY(A,i)
  }

只有当A[i]比它的直系孩子之一大时，你才会增加更多。而且您使用相同的索引重复出现，这意味着第二次调用将什么也不做。

我已经解释了heapify 这里的正确版本。

Answer 2

Java 实现。希望能帮助到你。

/**
 * Down-top heapify
 * @param index
 */
private void heapUp(int index){
    if(index > 1){
        int parent = index / 2;
        if(comp.compare(data[parent],data[index]) > 0 ){    
            swap(parent, index);
            heapUp(parent);
        }
    }
}
/**
 * Top-Down heapify
 * @param index
 */
private void heapDown(int index){
    int left = index * 2;
    int right = index *2 + 1;
    if( right >= size+1 && left >= size+1 ){ 
        data[size+1] = null;
        return;
    }

    int small = comp.compare(data[right],data[left]) >= 0 ? left : right;
    if(comp.compare(data[index],data[small]) >= 0){
        swap(small, index);
        heapDown(small);
    }
}

Answer 3

只需替换MIN_HEAPIFY(A,i)为，MIN_HEAPIFY(A,small)因为现在您需要转到大于 的节点的相应子节点A[i]，因为该索引现在很小，所以用小重复。