CS Studentzzz - 6 months ago 31

C++ Question

Simple question when I mess around with

cppreference and change the pop_heap

`std::vector<int> v { 60 , 20 , 50 , 10 , 5 , 30 , 45 };`

std::make_heap(v.begin(), v.end());

std::cout << "v: ";

for (auto i : v) std::cout << i << ' ';

std::cout << '\n';

std::pop_heap(v.begin(), v.end()); // moves the largest to the end

The result is:

v: 60 20 50 10 5 30 45

after pop_heap: 50 20 45 10 5 30 60

CPP Reference tells me that

I know I am missing something because if I read the would the first and last be swapped. I know that after everything is said and done the pop_heap will eliminate 60 but how is it that the order ends up the way it does. I think my not understand lies with last-1 but I cannot be sure

Answer

In `std::pop_heap`

you specify `first`

as `v.begin()`

, which returns an iterator pointing to the first element and `last`

as `v.end()`

which, according to cplusplus.com "Returns an iterator referring to the past-the-end element in the vector container.". That means that `last-1`

actually is the last element in your vector. So the elements that are swapped are the first (`60`

) and the last (`45`

). Afterwards the subrange [`first`

, `last-1`

), meaning everything BUT the last element (which is now `60`

) is made into a `heap`

again, meaning that the first element is the largest (`50`

).

So for the order it is garantied that the first element in your vector is `50`

and the last one is `60`

. As for the rest, cppreference states in the notes:

A max heap is a range of elements [f,l) that has the following properties:

- *f is the largest element in the range
- a new element can be added using std::push_heap()
- the first element can be removed using std::pop_heap()
The actual arrangement of the elements is implementation defined.

So the rest is just aranged in a way to that is convenient for implementation of the methods.