2

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

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

所以数组表示应该是90 36 17 25 26 7 1 2 3 19 代码的输出是

90 36 26 25 19 17 1 7 3 2

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

感谢您的解释

4

2 回答 2

0

为什么您希望您的堆以特定方式查看？有许多方法可以将这些输入数字排列成堆。你得到的结果也是一个有效的堆——每个父级都比它的子级大：

        90
    36      26
 25   19  17  1
7 3  2
于 2016-10-23T22:13:56.993 回答
0

最终堆结构将根据插入顺序和初始结构而有所不同。在您的情况下，2 7 26 25 19 17 1 90 3 36如果您从空堆开始，按给定顺序插入元素并在每次插入后堆放，则会产生您期望的结果。

此代码将产生您期望的结果：

std::vector<int> b = {2, 7, 26, 25, 19, 17, 1, 90, 3, 36};
auto it = b.begin();
while (it != b.end())
{
    std::make_heap(b.begin(), it+1);
    ++it;
}

但是，您的代码所做的是将所有元素预插入到堆中，然后对其进行排列，相当于：

std::vector<int> b = {2, 7, 26, 25, 19, 17, 1, 90, 3, 36};
std::make_heap(b.begin(), b.end());

两个结果同样有效。

于 2016-10-23T23:06:31.153 回答