CODEWITHSUNDEEP
c++
CS Studentzzz
CS Studentzzz

Reputation: 77

push, pop, and basic heap

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

Upvotes: 2

Views: 1656

Answers (2)

jotasi
jotasi

Reputation: 5177

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.

Upvotes: 1

Danh
Danh

Reputation: 6016

Like it said, swap first with last - 1 then do something like std::make_heap(first, last - 1)

Note: first and last are 2 parameters of std::pop_heap which is your v.begin() and v.end() respectively. It means that it will swap v.begin() and v.end() - 1 in your example.

See this example

Upvotes: 0

Related Questions