-1

アルゴリズム クラスの割り当てに HeapSort を実装して、ようやく完了しましたが、何らかの理由で、並べ替えが配列の最初の要素をスキップしています。

元の配列:

int heapArray[SIZE] = {  5 ,99, 32, 4, 1, 12, 15 , 8, 13, 55 };

HeapSort() 後の出力

5 99 32 15 13 12 8 4 1

すべての関数を調べましたが、最初の要素をスキップする理由がわかりません。誰でも私を助けることができますか？Iv には、以下のすべての HeapSort 関数が含まれています。私は見ることがたくさんあることを知っていますが、私はすっごく近くにあります。

int main()
{
int heapArray[SIZE] = {  5 ,99, 32, 4, 1, 12, 15 , 8, 13, 55 };
HeapSort(heapArray);


return 0;

}

................................................................... ...................................................

void HeapSort(int heapArray[])
{   
int heap_size = SIZE;
int n = SIZE;
int temp;

Build_Max_Heap(heapArray);

for(int i = n-1; i >= 2; i--)
{
    temp = heapArray[1];
    heapArray[1] = heapArray[i];
    heapArray[i] = temp;

    heap_size = heap_size-1;
    Max_Heapify(heapArray,1);
}

return;
}

................................................................... ...................................................

void Build_Max_Heap(int heapArray[])
{
double n = SIZE;

for(double i = floor((n-1)/2); i >= 1; i--)
{
    Max_Heapify(heapArray,i);
}

return;
}

................................................................... ...................................................

void Max_Heapify(int heapArray[],int i)
{
int n = SIZE;
int largest = 0;
int l = Left(i);
int r = Right(i);

if(( l <= n) && (heapArray[l] > heapArray[i]))
{
    largest = l;
}
else
{
    largest = i;
}

if( (r <= n) && ( heapArray[r] > heapArray[largest]))
{
    largest = r;
}

int temp;
if(largest != i)
{
    temp = heapArray[i];
    heapArray[i] = heapArray[largest];
    heapArray[largest] = temp;

    Max_Heapify(heapArray,largest);
}

return;
}

................................................................... ...................................................

int Parent(int i)
{
return (i/2);
}

int Left(int i)
{
return (2*i);
}

int Right(int i)
{
return ((2*i)+1);
}
4

3 に答える 3

1

コードにいくつかの問題があります。

まず、配列インデックスは1ではなく0から始まるため、インデックスエラーのある場所は次のように多くなります。

HeapSort関数の場合：

for(int i = n-1; i >= 2; i--)  {
                   //should be 1 not 2
    temp = heapArray[1]; //should be 0 not 1 in those 2 statements
    heapArray[1] = heapArray[i];
     heapArray[i] = temp;  
}

Max_Heapify(heapArray,1);
                  //should start from 0 not 1

その上：

for(double i = floor((n-1)/2); i >= 1; i--)
{                             //should start from 0 not 1
    Max_Heapify(heapArray,i);
}

親、左、右に同様のエラーがあります。上記の2つの投稿を確認できます。

その間、HeapSort関数とMax_Heapfiy関数に論理エラーがあります。heap_sizeを定義して更新しますが、実際に使用したことはありません。Max_Heapify関数に渡す必要があります。現在の最大要素を配列の最後に配置するたびに、ヒープ全体ではなく、残りの要素をヒープ化するだけで済みます。これは、heap_sizeを実際に使用したことがないため、heapify関数にエラーがあることも意味します。正しいHeapSortとMax_Heapify、およびBuild_Max_Heap関数は次のようになります。

ヒープソート：

void HeapSort(int heapArray[]) 
{   
  //do what you did before this sentence
  Build_Max_Heap(heapArray,heap_size); 
  //need to pass heap_size since Max_Heapify use heap_size
  for(int i = n-1; i >= 1; i--)
  {
     //...same as you did but pay attention to index
     heap_size = heap_size-1;
     Max_Heapify(heapArray,0,heap_size); //remember to use heap_size
   }
   //you declared void, no need to return anything
 }

Build_Max_Heap関数：

void Build_Max_Heap(int heapArray[], int heapSize) //should use heapSize
{
    int n = SIZE;
    for(int i = floor((n-1)/2); i >= 0; i--) //here should be 0 not 1
   {
      Max_Heapify(heapArray,i,heapSize); //should use heapSize
    }
 }

Max_Heapify関数：

void Max_Heapify(int heapArray[],int i, int heap_size) //should use heap_size
{
    //....here similar to what you did
    if(( l < heap_size) && (heapArray[l] > heapArray[i]))
    {   //^^compare with heap_size not SIZE
        //skip identical part
    }

    if( (r < heaps_ize) && ( heapArray[r] > heapArray[largest]))
    {
       //same error as above
    }

   //skip identical part again
   Max_Heapify(heapArray,largest, heap_size); //have to use heap_size
 }
}

擬似コードからヒープソートアルゴリズムをよりよく理解する必要があるかもしれません。

于 2013-03-18T01:31:00.930 に答える
0

ここ

Build_Max_Heap(heapArray);

for(int i = n-1; i >= 2; i--)
{                 ^^^^^
    temp = heapArray[1];
    heapArray[1] = heapArray[i];
    heapArray[i] = temp;

    heap_size = heap_size-1;
    Max_Heapify(heapArray,1);
}

return;
}

i=2 でループを停止し、1 に減らします。0でインデックス付けされた heapArray の最初の要素を使用しないでください。

于 2013-03-17T23:44:23.680 に答える
0

、および関数はParent、1 ベースの配列に適しています。0 ベースの場合は、次を使用する必要があります。LeftRight

int Parent(int i)
{
    return (i - 1) / 2;
}

int Left(int i)
{
    return (2 * i) + 1;
}

int Right(int i)
{
    return 2 * (i + 1);
}

サンプルヒープで確認できるように：

    0
   / \
  1   2
 / \ / \
3  4 5  6
于 2013-03-17T23:46:59.457 に答える