STL Heap Algorithms

Does the STL provide a heap container class?

No, it doesn't. Why not? Well, to have a separate heap container class would be redundant since a heap is just a vector in which the values have a certain arrangement. What it does have, instead, is some algorithms especially designed for working with vectors that are heaps, or that we want to be heaps.

What are the STL heap algorithms, and what do they do for us?

There are four STL algorithms that are quite useful when you are dealing with a heap structure:

• make_heap
• push_heap
• pop_heap
• sort_heap

As is often the case when dealing with the STL, not all of them work exactly the way you might guess they would.

For purposes of describing how they do work, assume we have a vector of integers v, of arbitrary size, and containing values in some arbitrary (random, or unsorted) order. We could also have an array, for example, and of course the component value does not have to be integer. Also, we assume we are dealing with a "maximum heap", but "minimum heaps" are also possible.

Each algorithm is shown in the form of a typical call to that algorithm. This does not show the return type, which is void in each case, nor the parameter types, both of which must be random access iterators. Each of the algorithms has a second version which takes a third parameter to indicate how comparison of elements is to be performed.

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

This algorithm converts the entire vector v into a heap.

push_heap(v.begin(), v.end());

This algorithm puts the element at position end()-1 into what must be a pre-existing heap consisting of all elements in the range [begin(), end()-1), with the result that all elements in the range [begin(), end()) will form the new heap. Hence, before applying this algorithm, you should make sure you have a heap in v, and then add the new element to the end of v via the push_back member function.

pop_heap(v.begin(), v.end());

This algorithm exchanges the elements at begin() and end()-1, and then rebuilds the heap over the range [begin(), end()-1). Note that the element at position end()-1, which is no longer part of the heap, will nevertheless still be in the vector v, unless it is explicitly removed.

sort_heap(v.begin(), v.end());

This algorithm sorts the elements in v, and should be used in preference to the "regular" STL sort algorithm when we know v to be a heap.