First of all: make_heap
, push_heap
, pop_heap
and sort_heap
are mostly heap "primitives", in "normal work" you generally use std::priority_queue
, which is way more straightforward to use (although it does have some other hideousnesses - namely, inability to directly access the underlying container and no equivalent of sort_heap
).
push_heap
and pop_heap
are designed to work on a generic iterator-determined range, and, as usual with STL algorithms (see e.g. the various std::remove_if
& co.), they cannot change the size of the underlying container (after all all you passed to them are a couple of iterators).
For this reason, push_heap
and pop_heap
will not actually add an element to the container, but will just patch up the order inside the range to include the new element/remove the top element and give back to the relevant range the "heap-property".
push_heap
expects to receive a range such that [first, last-1) is already a heap (i.e. it has the heap property), and the element to be added to the heap is stored in the last position of the range (i.e. last-1
). After push_heap
, the whole range [first, last) is now a heap, with the new element being added.
This is the reason why in the example it first does the push_back
(to put the new element ready to be manipulated by push_heap
), and then calls push_heap
.
On converse, pop_heap
will start with the range [first, last) considered as a heap, then do its things and at the end you'll get [first, last-1) being a heap, and in the last position (i.e. *(last-1)
) the highest element, extracted from the proper heap-range. That's why after the pop_heap
the example does pop_back
, reducing the vector size by 1, and thus discarding the extracted value, reducing the vector only to the range where it is an heap.
sort_heap
, instead, is used because, although a heap uses a particular ordering to achieve its performance characteristics, it does not keep the range sorted; sort_heap
destroys the heap (i.e. the range loses its heap properties) by sorting the elements (the sort exploits the heap properties, which potentially can give some performance gains over plain std::sort
).