-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

您的代码中有几个问题：

首先：数组索引从0开始，而不是1，因此，索引错误的地方很多，如下所示：

在堆排序函数中：

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

You Parent, Left 和 Right 有类似的错误，可以看上面两个帖子。

同时，您的 HeapSort 和 Max_Heapfiy 函数存在逻辑错误。您定义 heap_size 并更新它，但您从未真正使用过它。您必须将它传递给 Max_Heapify 函数。由于每次将当前最大的元素放在数组的末尾时，您只需要将剩余的元素堆起来，而不是整个堆。这也意味着您的 heapify 函数有错误，因为您从未真正使用过 heap_size。正确的 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
 }
}

您可能需要从伪代码中更好地理解 HeapSort 算法。

于 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，不要取 heapArray 的第一个元素，它的索引为0

于 2013-03-17T23:44:23.680 回答
0

,Parent和函数适用于基于 1 的数组Left。Right对于基于 0，您需要使用：

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 回答