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，循环继续，并且在这种情况下您明白它是如何工作的。

我认为最简单的情况是将这种情况视为一个堆，其中根只有一个孩子（其他所有节点都有两个孩子）。