Home > Net >  Max Heap is not created properly
Max Heap is not created properly

Time:05-19

I wrote the following code to build a maxheap from a already existing array the downadjust function makes the array a max heap but it is not producing results as desired Please check the code and tell me where am I going wrong also it would be very helpful if someone suggest what changes to the downadjust function will help me in making a min heap ( that is the next question that I have to code)

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

CodePudding user response:

Result for 5 1 9 2 11 50 6 100 7 is valid heap 100 11 50 7 5 9 6 2 1.

Perhaps you wanted 50 11 sequence and other ordered pairs of child nodes, but heap construction does not provide strict mutual ordering of children (as binary search tree does).

To make minheap, you just need to change two comparisons:

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