How to use std :: make_heap

Question

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

This is so confusing. To use heaps in std, you first put the elements in a vector, then call

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

What if I insert elements into a vector? Is the pile falling apart? For example, v can initially have 10 elements, and I make a bunch only from the third element to the 7th element, and now I insert elements in 5th place and 9th place, is the heap structure destroyed in the process?

And why should you first push_back(99) in this example before calling push_heap again? It looks like not only confusion, but also inefficiency.

What's the point of sort_heap() ? Should I sort the heap (what makes it right?)

Answer 1

First of all: make_heap , push_heap , pop_heap and sort_heap are basically heap primitives, in “normal work” you usually use std::priority_queue , which is easier to use (although it has some other disgusting abilities, namely: impossibility direct access to the base container and the equivalent of sort_heap ).

---

push_heap and pop_heap are designed to work with the general range defined by the iterator, and, as usual, with STL algorithms (see, for example, various std::remove_if and co.), they cannot resize the base container (after all, everything that you passed to them are a few iterators).

For this reason, push_heap and pop_heap will not actually add an element to the container, but simply close the order inside the range to include a new element / delete the top element and return the corresponding heap property range back.

push_heap expects to receive the range in such a way that [first, last-1] is already a heap (that is, it has a heap property), and the element to be added to the heap is stored at the last position (ie last-1 ) After push_heap entire range [first, last] is now a bunch with the addition of a new element.

That's why in this example, push_back is executed first (so that the new item is ready to be processed using push_heap ), and then it calls push_heap .

Otherwise, pop_heap will start from the range [of the first, last], considered as a heap, then perform its actions, and in the end you will get the [first, last-1] heap, and in the last position (i.e. *(last-1) ) the highest element extracted from the correct heap range. Therefore, after pop_heap in the example pop_back , decreasing the size of the vector by 1 and thus discarding the extracted value, reducing the vector only to the range where it is a heap.

sort_heap instead because, although the heap uses a specific order to achieve its performance characteristics, it does not preserve range sorting; sort_heap destroys the heap (i.e., the range loses its heap properties) by sorting the elements (sorting uses heap properties, which could potentially give some performance boost compared to regular std::sort ).

Answer 2

What if I insert elements into a vector? Heap confused?

Yes it is possible. If you click on a new element in a vector, you will get a new vector, which may no longer be a heap.

And why do you need to click on the button_pc (99) first before calling push_heap again? It looks like not only confusion, but also inefficiency.

No, this is not effective. std::vector::push_back complexity is almost constant. The real work is done by std::push_heap , which has a complexity of "no more than 2 × log (N)".

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

And what's the point of sort_heap ()? Should I sort the heap (what makes it right?)

There are only certain properties on the heap that make sorting easier, but they are not yet sorted. For example, this is a bunch:

And he is 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 saved.

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

And what's the point of sort_heap ()? Should I sort the heap (what makes it right?)

Nope! You must understand what a heap is. Thus, sort_heap() turns the heap into a range of sorted elements.