How to use std::make_heap [closed]

Question

http://www.cplusplus.com/reference/algorithm/push_heap/

It's so confusing. To use heaps in std, you first put the elements in a vector, then you call

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

What if I insert elements into the vector? Does the heap get messed up? For example v might initially have 10 elements, and I only make the heap from the 3rd element to the 7th element, and now I insert elements into the 5th place and 9th place, isn't the heap structure destroyed in the process?

And why do you have to push_back(99) first in the example, before calling push_heap again? Looks like not only confusing and also inefficient.

And what's the meaning of sort_heap()? Shouldn't the heap already be sorted, (that's what makes it a heap right?)

Answer 1

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).

Answer 2

What if I insert elements into the vector? Does the heap get messed up?

Yes, it could. If you push a new element in the vector, you get a new vector which, maybe, is not an heap anymore.

And why do you have to push_back(99) first in the example, before calling push_heap again? Looks like not only confusing and also inefficient.

No, it's not efficient. std::vector::push_back's complexity is pretty much constant. The real work is done by std::push_heap which has a complexity of "at most 2×log(N)".

Notice that std::make_heap and std::push_heap are very different. The first does not make assumption on the state of the container, the second assumes the elements in [begin, end-2) are already a valid heap (making it more efficient, in the case of a push_back).

And what's the meaning of sort_heap()? Shouldn't the heap already be sorted, (that's what makes it a heap right?)

A heap just have particular properties that make it easier to sort, but it's not already sorted. As an example, this is an heap:

And it's not sorted.

Answer 3

I find this documentation less confusing: http://en.cppreference.com/w/cpp/algorithm#Heap_operations

If you use std::push_heap() the heap-property is preserved.

If you insert one or more elements into the vector, then you must call std::make_heap() to restore the heap property.

And what's the meaning of sort_heap()? Shouldn't the heap already be sorted, (that's what makes it a heap right?)

Nope! You have to understand what an heap is. So sort_heap() turns a heap into a range of sorted elements.