What is the point of make_heap?

Question

Can someone please tell me the point of the STL heap function templates like std::make_heap? Why would anyone ever use them? Is there a practical use?

Answer 1

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