When should I use make_heap vs. Priority Queue?

Question

I have a vector that I want to use to create a heap. I'm not sure if I should use the C++ make_heap function or put my vector in a priority queue? Which is better in terms of performance? When should I use one vs. the other?

Answer 1

There's no difference in terms of performance. std::priority_queue is just an adapter class that wraps the container and the very same heap-related function calls into a class. The specification of the std::priority_queue openly states that.

By building a heap from an exposed std::vector and calling heap-related functions directly, you keep it open to the possibility of outside access, potentially damaging the integrity of the heap/queue. std::priority_queue acts as a barrier restricting that access to a "canonical" minimum: push(), pop(), top() etc. You can see it as self-discipline enforcing measure.

Also, by adapting your queue interface to the "canonical" set of operations, you make it uniform and interchangeable with other class-based implementations of priority queues that conform to the same external specification.

Answer 2

A priority_queue is (at least normally) implemented as a heap. As such, the real question is whether a priority_queue provides what you need. When you use make_heap you still have access to all elements. When you use priority_queue, you have only a few operations giving very limited access to elements (basically just insert an item, and remove the item at the head of the queue).

Answer 3

C++11 standard

C++11 N3337 standard draft specifies that std::make_heap is used to in the constructor of std::priority_queue at "23.6.4.1 priority_queue constructors":

explicit priority_queue

2 Effects: Initializes comp with x and c with y (copy constructing or move constructing as appropriate); calls make_heap(c.begin(), c.end(), comp).

And other methods say:

void push(const value_type& x);

Effects: c.push_back(x); push_heap(c.begin(), c.end(), comp)

As of the newer n4724 however, the wording for the non-constructor methods becomes "as if", so I think an actual call to *_heap methods is not guaranteed, just its functional behavior.

All of this confirms what https://stackoverflow.com/a/11266558/895245 mentioned about std::priority_queue being a wrapper around std::make_heap.

Step debug into g++ 6.4 stdlibc++ source to confirm that priority_queue forwards to make_heap

On Ubuntu's 16.04 default g++-6 package or a GCC 6.4 build from source you can step into the C++ library without any further setup.

Using that, we can easily confirm that std::priority_queue is just a wrapper over the std::make_heap family with an underlying std::vector, which implies that performance will be the same.

a.cpp:

#include <cassert>
#include <queue>

int main() {
    std::priority_queue<int> q;
    q.emplace(2);
    q.emplace(1);
    q.emplace(3);
    assert(q.top() == 3);
    q.pop();
    assert(q.top() == 2);
    q.pop();
    assert(q.top() == 1);
    q.pop();
}

Compile and debug:

g++ -g -std=c++11 -O0 -o a.out ./a.cpp
gdb -ex 'start' -q --args a.out

Now, if you step into the constructor std::priority_queue<int> q first it goes into a vector constructor, so we can already guess that the std::priority_queue contains an std::vector.

Now we run finish in GDB to find the queue constructor, and step into again, which leads us to the actual queue constructor /usr/include/c++/6/bits/stl_queue.h:

443       explicit
444       priority_queue(const _Compare& __x = _Compare(),
445              _Sequence&& __s = _Sequence())
446       : c(std::move(__s)), comp(__x)
447       { std::make_heap(c.begin(), c.end(), comp); }

Which clearly just forwards to std::make_heap on top of a c object.

So we open the source file in vim and find the definition of c:

  template<typename _Tp, typename _Sequence = vector<_Tp>,
       typename _Compare  = less<typename _Sequence::value_type> >
    class priority_queue
    {

      [...]

      _Sequence  c;

and so we conclude that c is a vector.

If we step into the other methods, or by inspecting the source further, we easily see that all other priority_queue methods also just forward to the std::make_heap family of functions.

The choice of a heap vs say, a balanced BST, makes sense since the average insert time is smaller for the heap, see: Heap vs Binary Search Tree (BST)

Answer 4

priority_queue is not a container. It is a container adapter that uses a specific underlying container, e.g. vector or deque, and provides a specific set of methods to work with the data. Moreover, its implementation relies on the *_heap algorithms.

For example, whenever you push a new value to the vector you should call push_heap to extend a range considered as a heap. If you do not use the priority_queue, it allows you to consider, say, a half of the vector as a heap (std::make_heap(v.begin(), v.begin() + (v.size() / 2))), whereas another half will be as-is.

What priority_queue does when you call push on it: it pushes a new element to the back of underlying container and calls push_heap to keep the heap property prioritized (it only matters the first element to be the greatest).

I would say that you'd better consider the solution design and your specific requirements, rather than performance issues.

Answer 5

If you don't want to modify that vector then you should use priority queue as it creates a separate vector. But, if you can afford to edit it, then obviously using make_heap would be better as it doesn't create an auxiliary space and modify that vector in-place and would therefore, save space. Moreover, Priority queue is easy to implement. For example, when you use make_heap while popping an element you have to use two commands, firstly pop_heap and then pop_back.. but you can do it with just one command in case of priority queue. Similarly, while pushing the element into the heap.

Now, the performance of both would be same because priority queue is not a container and it uses some underlying container as vector or deque which uses same heap operations as used by make_heap operations.. So,you should use one depending on your requirement.

Answer 6

make_heap allows for flexibility at the cost of encapsulation, as an example, printing out the heap.

An interesting use of make_heap is an in place merge sort that uses make_heap on one side of the merge, to achieve a worst case in place merge of n/2(log(n/2)).

This example shows the use of the input vector and printing out the created heap:

#include <queue>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

void print(string prefix,vector<int>& v)
{
  cout << prefix;
  for(int i : v)
     cout << i << " ";
  cout << endl;
}

int main()
{
  vector<int> v={1,2,9,0,3,8,4,7,1,2,9,0,3,8,4,7};
  typedef priority_queue< int,vector<int>,greater<int> > MinQ;
  MinQ minQ(v.begin(),v.end()); //minQ
  print("After priority_queue constructor: ",v);

  make_heap(v.begin(),v.end(),greater<int>());
  print("After make_heap: ", v);
  return 0;
}

Output:

After priority_queue constructor: 1 2 9 0 3 8 4 7 1 2 9 0 3 8 4 7
After make_heap: 0 1 0 1 2 3 4 7 2 3 9 8 9 8 4 7