C++ heapsort混淆

Question

這可能是一個奇怪的問題，但我想弄清楚爲什麼下面的代碼工作。

看起來好像應該在堆元素索引從1開始，但從0開始並且排序正確完成時使用此代碼。

我說因爲左邊的孩子計算爲（元素* 2），右邊的孩子是（元素* 2 + 1）。這將使左子爲索引爲0的元素也具有索引0

#include <iostream> 
using namespace std; 

void siftDown(int numbers[], int root, int bottom) { 
    int done, maxChild, temp; 
    done = 0; 
    while ((root*2 <= bottom) && (!done)) { 
     if (root*2 == bottom) 
      maxChild = root * 2; 
     else if (numbers[root*2] > numbers[root*2 + 1]) 
      maxChild = root * 2; 
     else 
      maxChild = root * 2 + 1; 

     if (numbers[root] < numbers[maxChild]) { 
      temp = numbers[root]; 
      numbers[root] = numbers[maxChild]; 
      numbers[maxChild] = temp; 
      root = maxChild; 
     } else { 
      done = 1; 
     } 
    } 
} 

void heapSort(int numbers[], int n) { 
    int i, temp; 

    for (i = n/2; i >= 0; i--) { 
     siftDown(numbers, i, n - 1); 
    } 

    for (i = n-1; i >= 1; i--) { 
     temp = numbers[0]; 
     numbers[0] = numbers [i]; 
     numbers [i] = temp; 
     siftDown(numbers, 0, i-1); 
    } 
} 

int main() { 
    int cases; 
    int n; 
    int count; 

    cin >> cases; 

    for (int i=0; i < cases; i++) { 
     cin >> n; 
     int array[n]; 
     for (int j=0; j < n; j++) { 
      cin >> array[j]; 
     } 

     heapSort(array, n); 
     for (int k=0; k < n; k++) { 
      cout << array[k]; 
     }  
     cout << endl; 
    } 
} 

Answer 1

對於情況下，當根= 0時，有兩種子情況：號碼[0]>號[1]，或不。在第一個中，maxchild設置爲0.下一個「if」子句 - 實際上「數字[0] <數字[0]」 - 必然計算爲false，因此「done」設置爲1並且循環終止。

如果numbers [1]> = numbers [0]，則maxchild設置爲1.下一個子句變爲「numbers [0] < numbers [1]」，如果數字[0] ] ==數字[1]。如果它是假的，循環像以前一樣終止。如果它是真的，則交換數字[0]和數字[1] - 因此更大的數字正確地移動到堆頂部 - 並且root變成1，循環繼續，並且在這種情況下您明白它是如何工作的。

我認爲最簡單的情況是將這種情況視爲一個堆，其中根只有一個孩子（其他所有節點都有兩個孩子）。