最大堆未正确创建

Question

我写了下面的代码来从一个已经存在的数组中构建一个 maxheap downadjust 函数使数组成为一个最大堆，但它没有产生预期的结果请检查代码并告诉我我哪里出错了，如果有人建议对 downadjust 函数进行哪些更改将帮助我制作最小堆（这是我必须编写的下一个问题），这将非常有帮助

#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;
}

Answer 1

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

也许您想要 50 11 序列和其他有序的子节点对，但堆构造不提供子节点的严格相互排序（如二叉搜索树那样）。

要做minheap，只需要改两个比较：

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

最大堆未正确创建

Max Heap is not created properly

c++

algorithm

heap

max-heap