What is the point of make_heap?

Question

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

Answer 1

They are used to construct and maintain the Heap data structure

Answer 2

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.

Answer 3

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.

Answer 4

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

Answer 5

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

Answer 6

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.