c++ - Max Heap 未正确创建

我编写了以下代码来从已经存在的数组构建一个 maxheap downadjust 函数使数组成为 max heap 但它没有产生所需的结果 请检查代码并告诉我我哪里出错了如果有人建议对 downadjust 函数进行哪些更改将有助于我制作 min heap (这是我必须编写的下一个问题)

#include <iostream>

using namespace std;

void downadjust(int heap[],int i){
    // n is size
    int n=heap[0];
    int j,flag=1;
    while(2*i<=n && flag==1){
        j=2*i;
        if(j+1<=n && heap[j+1]>heap[j]){
            j=j+1;
        }
        if(heap[i]>heap[j]) flag=0;
        else
        {
            swap(heap[i],heap[j]);
            i=j;
        }
    }
}

void disp(int heap[],int n){
    for(int i=1;i<n;i++){
        cout<<heap[i]<<" ";
    }
}

int main()
{
    int n;
    cout<<"no of stud";
    cin>>n;
    n++;
    int heap[n];
    heap[0]=n-1;
    
    for(int i=1;i<n;i++){
        cin>>heap[i];
    }
   
    for(int i=n/2;i>=1;i--){
        downadjust(heap,i);
    }
    
    disp(heap,n);
    
    cout<<endl;
    
    cout<<"max is "<<heap[1];

    return 0;
}

回答1

5 1 9 2 11 50 6 100 7 的结果是有效的 heap 100 11 50 7 5 9 6 2 1

也许您想要 50 11 序列和其他有序的子节点对,但 heap 构造不提供严格的子节点相互排序(就像二叉搜索树一样)。

要制作minheap,您只需要更改两个比较:

if (j + 1 <= n && heap[j + 1] < heap[j]) {
        j = j + 1;
    }
    if (heap[i] < heap[j]) flag = 0;