CS Studentzzz CS Studentzzz - 1 year ago 105
C++ Question

push, pop, and basic heap queston

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

std::pop_heap-Swaps the value in the position first and the value in the position last-1 and makes the subrange [first, last-1) into a max heap. This has the effect of removing the first (largest) element from the heap defined by the range [first, last).

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 Source

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.