What is the point of make_heap?

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?

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

std::make_heap should almost never be used in practice. While it is true that heaps are useful for priority queues, that doesn't explain why you would want to manually maintain the structure. std::priority_queue has a much more useful interface if all you need is a priority queue.

If you use make_heap and its siblings directly, you have to make sure to use them every single time you make a change to the underlying container. I have seen them used two or three times and every single time they were used incorrectly.

I have only used the heap operations directly once myself, because I needed to use a vector as a priority queue for a while and then sort it. You will most likely never need std::make_heap.

If you need a priority queue with the ability to change elements, you can use std::set. You can get the smallest or largest element with *s.begin() or *s.rbegin() respectively and update an element by removing the old value and inserting the new one.

There are essentially two ways to construct a [binary] heap: create an empty heap and insert each element into it one at a time, or take a range of values and heapify them.

Each push operation on a heap takes O(logn) time so if you are pushing N items onto a heap it will take O(NlogN) time. However to build a binary heap from an array of values takes only O(N) time.

Thus it makes more sense to insert each element into an array (or other container that supports random access iterators) and then call make_heap() on the array than it does to maintain the heap structure while inserting.

In addition to the above, the STL's sorting algorithm is introsort, which is a mixture of quicksort and heapsort (it fails over from quicksort to heapsort if the former is doing poorly). make_heap creates a heap structure, which is needed for running heapsort, which is needed for introsort.

They are used to construct and maintain the http://en.wikipedia.org/wiki/Heap_(data_structure)">Heap data structure