为什么我的HeapSort会跳过数组中的第一个元素？

Question

Im在我的算法类中为一个赋值实现了HeapSort，最后Im完成了，但由于某种原因，这个排序正在跳过我的数组中的第一个元素。

原始阵列：堆排序后

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

输出（）

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

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

你父母，左，右有类似的错误，你可以看到上面的两个职位。

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

Answer 2

这里

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，不采取其通过

Answer 3

的Parent，索引heapArray的第一元件3210和Right函数适用于基于1的阵列。对于基于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