There are two main ways to work with heaps in C++. Both ways require only machinery already available in the Standard Template Library (STL). The first way is to use the STL container std::priority_queue since it already contains most of the functionality a heap should have. Another way is to use an std::vector (actually any container which has random-access iterators) to store the heap elements and use the functions std::make_heap, std::push_heap and std::pop_heap to arrange the elements of the vector into a valid heap, then push and pop elements from the vector while keeping it a valid heap. Only the first approach will be covered in this post; a future post will cover the second technique.

Heaps based on std::priority_queue

Before we go through code examples, a little bit of theory is in place here. A priority queue is an abstract data type consisting of a queue of elements with each element having a "priority" associated to it. For instance, a set of tasks which are given different priority values and must be completed in a "higher priority first" fashion can be naturally represented as a priority queue. A heap is an efficient implementation of a priority queue in the same way as a linked list is an implementation of the abstract list data type. Since heaps are by far the most common implementations of priority queues, they are often used as synonyms of each other.

Here is the declaration of the std::priority_queue class template:

template<
	class T,
	class Container = std::vector<T>,
	class Compare = std::less<typename Container::value_type>
> class priority_queue;

As the declaration shows, std::priority_queue is a class template which needs three template parameters: T specifies the type of the stored elements, Container specifies the type of the container which will hold these elements (std::vector<T> being used by default) and Compare is a comparison class which the user must provide to specify an order relation for the elements of the priority queue. Compare defaults to std::less<T>, which is a class containing the following member function:

bool operator() (const T& x, const T& y)
{
	return x < y;
}

Using std::less, we can compare two values as shown below:

#include <functional>
#include <iostream>

int main()
{
	std::less<int> compare;
	std::cout << std::boolalpha
	          << compare(2,3) << "\n"  /* (2 < 3) == true */
	          << compare(3,2) << "\n"; /* (3 < 2) == false */

	return 0;
}

We may also generate instances of std::less only when they are needed. To exemplify, the code below generates the same output as the code above, but objects of type std::less<int> are constructed directly at the places where we need them:

#include <functional>
#include <iostream>

int main()
{
	std::cout << std::boolalpha
	          << std::less<int>()(2,3) << "\n"  /* (2 < 3) == true */
	          << std::less<int>()(3,2) << "\n"; /* (3 < 2) == false */

	return 0;
}

Classes like std::less are called functor classes since they can be used with a syntax similar to that of functions.

The std::priority_queue container sorts its elements in a way which keeps the "largest element" (according to the Compare class) on the top, i.e., the element x such that Compare(x,y) == false for every other stored element y is the top element (if multiple copies of the "largest element" exist, any one of them may be the top element). Since we can provide a comparison class to specify any ordering we want, we can make std::priority_queue behave as a min-heap as well. But before we do that, let's first see how std::priority_queue works by default (as a max-heap):

#include <queue>
#include <iostream>

int main()
{
	std::priority_queue<int> Q;

	Q.push(3);
	Q.push(4);
	Q.push(2);
	Q.push(1);

	while (Q.empty() == false)
	{
		/* print the top element, then remove it */
		std::cout << Q.top() << " ";
		Q.pop();
	}
	std::cout << "\n";

	return 0;
}

Since std::priority_queue is by default a max-heap, the output of this program is:

4 3 2 1

Notice that line 6 of the code above is equivalent to this:

std::priority_queue<int, std::vector<int>, std::less<int>> Q;

To turn Q into a min-heap, all we need to do is use std::greater<int> instead of the default std::less<int>. Just like std::less, std::greater is also a functor class but with the following member function:

bool operator() (const T& x, const T& y)
{
	return x > y;
}

As the highlighted line shows, the only difference to std::less is the fact that the value of (x > y) is returned instead of the value of (x < y). Here is the same code from above with Q now being a min-heap:

#include <queue>
#include <iostream>

int main()
{
	std::priority_queue<int, std::vector<int>, std::greater<int>> Q;

	Q.push(3);
	Q.push(4);
	Q.push(2);
	Q.push(1);

	while (Q.empty() == false)
	{
		/* print the top element, then remove it */
		std::cout << Q.top() << " ";
		Q.pop();
	}
	std::cout << "\n";

	return 0;
}

Not surprisingly, the output of this program is:

1 2 3 4

One point must be emphasized here: both std::less and std::greater work only for objects which have an order defined by the comparison operators < and > respectively. This means that if you try to store objects which are instances of a class for which the operators < and > are not defined, your code will not compile. However, you can provide your own functor class to define an order for the class objects:

#include <queue>
#include <iostream>

struct Integer
{
	Integer(const int __x): x(__x) { }
	int x;
};

/* functor class which defines the order for Integer objects */
struct Order
{
	bool operator()(const Integer& a, const Integer& b)
	{
		return a.x > b.x;
	}
};

int main()
{
	std::priority_queue<Integer, std::vector<Integer>, Order> Q;

	Q.push(Integer(3));
	Q.push(Integer(4));
	Q.push(Integer(2));
	Q.push(Integer(1));

	while (Q.empty() == false)
	{
		/* print the top element, then remove it */
		std::cout << Q.top().x << " ";
		Q.pop();
	}
	std::cout << "\n";

	return 0;
}

Since Order is constructed similarly to std::greater (but compares objects of type Integer by comparing the values of their x members), it should not be surprising that the output of the program above is:

1 2 3 4

Bonus: run-time complexity of heap construction

Whenever the elements which will be inserted in the heap are known in advance, it is better to build the heap directly from these elements instead of building it by inserting one element at a time. For instance, if $n$ elements are inserted as we did above, the run-time complexity will be $O(n\log(n))$, but if all elements are known in advanced and stored, say, on a vector, we can build the heap in $O(n)$ time using the heapify method. The std::priority_queue container has a constructor which already does this for us:

int main()
{
	/* elements first stored on a random-access container */
	std::vector<int> V = { 1, 2, 3, 4, 5, ... };

	/* build heap using heapify method (linear run-time complexity) */
	std::priority_queue<int> Q(V.begin(), V.end());

	...
}