爲什麼我的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