What is the point of make_heap?

Your direct question would be well-answered by a class in algorithms and data structures. Heaps are used all over the place in algorithms in computer science. To quote from the make_heap function linked below, "a heap is a tree where each node links to values not greater than its own value." While there are lots of applications for a heap, the one that I use most frequently is in search problems when you want to keep track of a sorted list of N values efficiently.

I had similar confusion to yours when I first encountered the STL heap functions. My question was a little bit different though. I wondered "Why isn't the STL heap in the same class of data structures as std::vector?" I thought that it should work like this:

std::heap< int > my_heap;
my_heap.heap_insert( 7 );
my_heap.heap_insert( 3 );

The idea behind the STL heap functions though is that they allow you to make a heap data structure out of several different underlying STL containers, including std::vector. This can be really useful if you want to pass around the container for use elsewhere in your programs. It's also a little bit nice, because you can choose the underlying container of your heap if you so choose to use a something other than std::vector. All you really need are the following:

template <class RandomAccessIterator>
  void make_heap ( RandomAccessIterator first, RandomAccessIterator last );

This means that you can make lots of different containers into a heap A comparator is also optional in the method signature, you can read more about the different things that you can try in the STL pages for the make_heap function.

Links:

• Heap Data Structure
• make_heap function

If you want to make a priority queue out from a list, well, you can use make_heap:

Internally, a heap is a tree where each node links to values not greater than its own value. In heaps generated by make_heap, the specific position of an element in the tree rather than being determined by memory-consuming links is determined by its absolute position in the sequence, with *first being always the highest value in the heap.

Heaps allow to add or remove elements from it in logarithmic time by using functions push_heap and pop_heap, which preserve its heap properties.

You are supposed to use std::make_heap() along with std::push_heap() and std::pop_heap() to maintain a binary heap on top of a vector or array; the latter two functions maintain the heap invariant. You can also use std::heap_sort() to sort such a heap. While it is true that you could use std::priority_queue for a priority queue, it doesn't let you get at the insides of it, which perhaps you want to do. Also, std::make_heap() and std::heap_sort() together make a very simple way of doing heapsort in C++.