c++ - 最大堆的数组表示

Question

我正在尝试创建一个最大堆，逻辑很简单，如果父项小于其子项之一，则交换它们。我尝试使用

实现它

void maxHeapify( int i , int *a , int n ){

    int largest = i;
    int left    = ( i * 2 ) + 1;
    int right    = ( i * 2 ) + 2;

    if( left < n && a[ largest] < a[ left ])
        largest = left;
    if( right < n  && a[ largest ] < a[right])
        largest = right;
    if( largest != i ){
        swap( a[i], a[largest]);
        maxHeapify( largest , a,  n );
    }
}


int main(){
    int n;
    int * a;
    cout << "Number of elements : ";
    cin >> n ;
    a = new int[n];
    for( int i = 0; i < n ; i++){
        cin >> a[i];
    }

    for( int i = n/2 -1 ; i >= 0 ; i-- ){
        maxHeapify( i , a, n);
    }
    for(int i = 0; i < n ; i++){
        cout << a[i] << " ";
    }

    return 0;
}

我正在使用输入

2 7 26 25 19 17 1 90 3 36

这棵树应该是这样的

        90      36    17   25   26 7   1 2   3 19

so array representation should be 90 36 17 25 26 7 1 2 3 19yet the output of the code is

90 36 26 25 19 17 1 7 3 2

我查了一下，在很多教程中发现了很多相同的代码。为什么输出不是数组中树的表示？我是不是理解错了？

感谢解释

Answer 1

为什么您希望您的堆以特定方式显示？可以通过多种方式将这些输入数字排列成堆。您得到的结果也是一个有效的堆 - 每个父项都比其子项大:

        90
    36      26
 25   19  17  1
7 3  2