C++ output order

Question

I wrote the following program to implement min heap data structure but am not getting the expected output.

#include <iostream>
#include <iomanip>
#include <vector>

using namespace std;

class MinHeap
{
    vector<int> heap;
    int size;

public:
    MinHeap()
    {
        //cout<<"asc";
        size=0;
    }

    void insert(int n); 
    void heapify(int i);
    int extract_min();  

    int get_size()
    {
        return size;
    }
};

void MinHeap::insert(int n)
{
    int i=size, parent;
    parent=(i-1)/2;
    heap.push_back(n);
    size++;

    while(i>0)
    {
        if(heap[i]<heap[parent])
        {
            swap(heap[i], heap[parent]);            
        }
        else
            break;
        i=parent;
        parent=(i-1)/2;
    }
}

void MinHeap::heapify(int i)
{
    int left=2*i+1, right=2*i+2, min_index=i;

    if(left<size && heap[left]<heap[min_index])
        min_index=left;
    if(right<size && heap[right]<heap[min_index])
        min_index=right;
    if(min_index!=i)
    {
        swap(heap[i], heap[min_index]);
        heapify(min_index);
    }
}

int MinHeap::extract_min()
{
    int i=size-1, temp;

    if(i>=0)
    {
        temp=heap[0];
        heap[0]=heap[i];
        size--;
        heapify(0);

    }
    return temp;
}



int main()
{

    int n, i, last=0, val, j;
    MinHeap h;  
    h.insert(10);
    h.insert(5);
    h.insert(7);
    h.insert(1);
    cout<<h.extract_min()<<" "<<h.extract_min()<<" "<<h.extract_min()<<" "<<h.extract_min();
    // cout<<h.extract_min()<<"\n";
    // cout<<h.extract_min()<<"\n";

    return 0;
}

Output: 10 7 5 1

Expected Output: 1 5 7 10

However I get the expected output when I print them in different lines(as I have done in the commented lines, just above return 0 in main).

Sorry if I missed something too trivial.

Also note that the standard library already has some functions to manage heaps, such as [`std::make_heap`](http://en.cppreference.com/w/cpp/algorithm/make_heap). — Holt, Dec 19 '16 at 10:04
Thanks. It says it constructs `Max Heap`, which library to use for `Min Heap`(or should I just give provide the suitable `comp` function as an argument)? — shiva, Dec 20 '16 at 07:45
You should just provide a suitable `comp` (e.g. `std::greater`). — Holt, Dec 20 '16 at 07:48

score 4 · Accepted Answer · answered Dec 19 '16 at 10:04

4

h.extract_min() obviously changes the variable h. So, here you have multiple changes of the same variable within one statement. Unfortunately, C++ standard does not specify the execution order in the statements, so, different calls to h.extract_min() are not necessarily executed in left-to-right manner (in fact, you have right-to-left order, but it's just luck).

To have correct output and readable code, consider using loops:

for (int i = 0; i < 4; ++i) {
    cout << h.extract_min() << ' ';
}

answered Dec 19 '16 at 10:04

alexeykuzmin0

6,344
2
28
51

By this: `C++ standard does not specify the execution order in the statements`, do you mean the statements within `cout`? – shiva Dec 20 '16 at 07:46
@shiva Yes. `cout< – alexeykuzmin0 Dec 20 '16 at 07:50

Alexey Subbota · Answer 2 · 2016-12-19T10:20:39.503

Order of evaluation of the operands of almost all C++ operators (including the order of evaluation of function arguments in a function-call expression and the order of evaluation of the subexpressions within any expression) is unspecified. The compiler can evaluate operands in any order, and may choose another order when the same expression is evaluated again.

http://en.cppreference.com/w/cpp/language/eval_order

C++ output order

2 Answers2