Maxheap giving wrong result

Question

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

no of stud => implies No of Students as in my problem I am supposed to take marks of n number of students — , May 18 '22 at 16:15
`cin>>n; n++;int heap[n];` -- This is not valid C++. Arrays in C++ must have their size denoted by a constant expression, not a runtime value. Dynamic arrays in C++ are achieved by using `std::vector heap(n);` — PaulMcKenzie, May 18 '22 at 16:20
in heap[0] i am storing the number of students i.e number of entries in the array I am not using 0'th location of array for storing any data only size is stored in that I hope this clear your doubt — , May 18 '22 at 16:20
`std::make_heap(heap.begin() + 1, heap.end());` -- That is a one line solution. See [std::make_heap](https://en.cppreference.com/w/cpp/algorithm/make_heap). — PaulMcKenzie, May 18 '22 at 16:23
can anyone just tell me with the same code what changes would give me the expected result — , May 18 '22 at 16:23
Why do you think that program is wrong? `6 1 3 9 4 2 5 7` gives valid heap `9 7 5 6 4 2 3 1` — MBo, May 18 '22 at 16:23
Paul that's so nice of you for suggesting a one linear solution but we are not allowed( at college level) to use inbult func. or stl we are asked to write the core logic as we are still in our initial stages of learning — , May 18 '22 at 16:24
@Athrav_N *but we are not allowed* -- But you are allowed to use invalid, non-standard C++?? So how are you going to create the dynamic array? The only other option is to use `new[]/delete[]`. — PaulMcKenzie, May 18 '22 at 16:25
MBo for the input (9 size ) 5 1 9 2 11 50 6 100 7 its giving wrong result — , May 18 '22 at 16:26
@Athrav_N [What is a debugger?](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems). Second, just for fun, compare your output with what `std::make_heap` produces. Is it the same? If it is, what's the issue? You should use whatever it takes to verify what you have actually works, and utilizing `std::make_heap` gives you assurance as to whether your home-made code actually works or not. — PaulMcKenzie, May 18 '22 at 16:28
I am trying to say for the input 5,1,9,2,11,50,6,100,7 the output should have been 100 50 11 7 2 9 6 1 5 but its not producing that — , May 18 '22 at 16:31
No, it shouldn't! You cannot expect left-right ordering of children — MBo, May 18 '22 at 16:32
Got that MBo thanks for that , Also thanks Paul for the idea, can you guys help me make minor changes in same code to create a min heaap — , May 18 '22 at 16:35
@Athrav_N -- *for the input 5,1,9,2,11,50,6,100,7 the output should have been 100 50 11 7 2 9 6 1 5* -- It's time to verify your expectations using `std::make_heap`. [See this](https://godbolt.org/z/zGjsocMf7) — PaulMcKenzie, May 18 '22 at 16:36
Thanks for that Paul and I got that now just a fun fact I thought my result is wrong because the book I was referring to had the wrong solution to the problem so I was thinking my program is wrong ☺️ — , May 18 '22 at 16:39
Can you guys help me with the last thing of making changes to create min heap using same code — , May 18 '22 at 16:40
@Athrav_N -- You have to make the attempt. One hint is that if you look at `std::make_heap`, to get a min-heap, all that is required is to set the comparison to do a "greater than" instead of "less than". See [this](https://godbolt.org/z/zosPdffvq). So make that similar change to the code you have now. — PaulMcKenzie, May 18 '22 at 16:44
@Athrav_N The book might have a different code that results in a different heap. For any input there are many solutions that are correct heaps. — Goswin von Brederlow, May 18 '22 at 17:00
@Athrav_N -- In addition, by using `std::make_heap` as a checking tool, you have something to prove your output is correct if your teacher concludes that your output is incorrect. — PaulMcKenzie, May 18 '22 at 18:04

score 0 · Accepted Answer · answered May 18 '22 at 16:48

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;

Maxheap giving wrong result

1 Answers1