0

次の MIN_HAPIFY アルゴリズムは正しいですか?

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)
  }
}
4

3 に答える 3

1

いいえ、それは正しくありません。

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

A[i]がその直接の子の 1 つよりも大きい場合にのみ、さらにヒープ化します。そして、同じインデックスで再帰します。つまり、2 番目の呼び出しは何もしません。

heapify hereの正しいバージョンを説明しました。

于 2013-03-03T16:46:23.590 に答える
0

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);
    }
}
于 2013-03-04T18:30:20.193 に答える