In a previous post, the std::priority_queue container was introduced since it provides most of the functionality a heap should have. This post presents another way of working with heaps which is more flexible, but perhaps less clean from a software engineering perspective since it is less modular than the approach we presented earlier and also provides no encapsulation of the heap elements. This approach consists in using any container which has random-access iterators (e.g. std::vector) to store the heap elements and using the STL functions std::make_heap, std::push_heap and std::pop_heap to arrange the elements of the container into a valid heap, then push and pop elements from the container while keeping it a valid heap. In what follows, we will give complete examples of how this can be done.

The techniques shown here expose some of the inner workings of the heap data structure implemented in an array (which is by far the most common one). For instance, we insert a new element into the heap by placing it at the array position following the last heap element and then "bubbling up" this element until it reaches a valid position, at which point the array is again arranged as a valid heap. Similarly, we pop the root element from the heap (which is the largest/smallest element for max-/min-heaps respectively) by swapping it with the rightmost element on the array, deleting it and then "bubbling down" the element placed at the root of the heap until it reaches a valid position. This is exactly how std::push_heap and std::pop_heap work. The example below clarifies this:

#include <vector>
#include <algorithm>
#include <iostream>

int main()
{
	/* heap elements are stored on a random-access container */
	std::vector<int> Q;

	/*
	 * for each value x in {3,4,2,1}, insert x at the end of the
	 * array, then restore the heap property by "bubbling it up"
	 */
	Q.push_back(3);
	std::push_heap(Q.begin(), Q.end());

	Q.push_back(4);
	std::push_heap(Q.begin(), Q.end());

	Q.push_back(2);
	std::push_heap(Q.begin(), Q.end());

	Q.push_back(1);
	std::push_heap(Q.begin(), Q.end());

	while (Q.empty() == false)
	{
		std::cout << Q.front() << " ";

		/*
		 * swap the root and the rightmost array element, then
		 * "bubble down" the element placed at the root
		 */
		std::pop_heap(Q.begin(), Q.end());

		/* remove the last array element (previous root) */
		Q.pop_back();
	}
	std::cout << "\n";

	return 0;
}

By default, std::push_heap and std::pop_heap rearrange the array elements in a way which places its "largest element" (according to the order defined by the operator < for the heap elements) on the leftmost position of the array, i.e., the element x such that (x < y) == false for every other stored element y is the first array element (if multiple copies of the "largest element" exist, any one of them may be the first element). This is why we print this "largest element" of the heap by printing the value of Q.front(). The output of the program above is:

4 3 2 1

Both std::push_heap and std::pop_heap can also take a comparison function as input to define the order relation for the elements of the heap. For instance, the example below shows one way to turn the heap into a min-heap:

#include <vector>
#include <algorithm>
#include <iostream>

bool compare_ints(const int& x, const int& y)
{
	return x > y;
}

int main()
{
	/* heap elements are stored on a random-access container */
	std::vector<int> Q;

	/*
	 * for each value x in {3,4,2,1}, insert x at the end of the
	 * array, then restore the heap property by "bubbling it up"
	 */
	Q.push_back(3);
	std::push_heap(Q.begin(), Q.end(), compare_ints);

	Q.push_back(4);
	std::push_heap(Q.begin(), Q.end(), compare_ints);

	Q.push_back(2);
	std::push_heap(Q.begin(), Q.end(), compare_ints);

	Q.push_back(1);
	std::push_heap(Q.begin(), Q.end(), compare_ints);

	while (Q.empty() == false)
	{
		std::cout << Q.front() << " ";

		/*
		 * swap the root and the rightmost array element, then
		 * "bubble down" the element placed at the root
		 */
		std::pop_heap(Q.begin(), Q.end(), std::greater<int>());

		/* remove the last array element (previous root) */
		Q.pop_back();
	}
	std::cout << "\n";

	return 0;
}

From compare_ints, we see that the element x which satisfies compare_ints(x,y) == false for all other y in the array must be the smallest element. Since this element is the one placed at the leftmost array position (the "top" of the heap), we have then turned the heap into a min-heap, so the output now becomes:

1 2 3 4

Another way of achieving the same result is by passing an instance of std::greater<int> as the comparison function object. As mentioned on part 1, std::greater is a functor class which contains the following member function (compare it with the definition of compare_ints above):

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

Since functor class objects can be used in places where functions are expected (hence the name), we can use an instance of std::greater whenever comparison function objects are expected. The code below illustrates this point:

#include <vector>
#include <algorithm>
#include <functional>
#include <iostream>

int main()
{
	/* heap elements are stored on a random-access container */
	std::vector<int> Q;

	/*
	 * for each value x in {3,4,2,1}, insert x at the end of the
	 * array, then restore the heap property by "bubbling it up"
	 */
	Q.push_back(3);
	std::push_heap(Q.begin(), Q.end(), std::greater<int>());

	Q.push_back(4);
	std::push_heap(Q.begin(), Q.end(), std::greater<int>());

	Q.push_back(2);
	std::push_heap(Q.begin(), Q.end(), std::greater<int>());

	Q.push_back(1);
	std::push_heap(Q.begin(), Q.end(), std::greater<int>());

	while (Q.empty() == false)
	{
		std::cout << Q.front() << " ";

		/*
		 * swap the root and the rightmost array element, then
		 * "bubble down" the element placed at the root
		 */
		std::pop_heap(Q.begin(), Q.end(), std::greater<int>());

		/* remove the last array element (previous root) */
		Q.pop_back();
	}
	std::cout << "\n";

	return 0;
}

Since std::greater behaves exactly as the function compare_ints, the output of the program above is not affected by the changes we just made:

1 2 3 4

Run-time complexity of heap construction

Just as we mentioned on part 1 of this post, a heap can be constructed in time $O(n)$ instead of $O(n\log(n))$ if we first store the heap elements on an array and then rearrange the array elements using the heapify method to turn it into a valid heap. This is what std::make_heap does:

#include <vector>
#include <algorithm>
#include <iostream>

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

	/* heapify Q (linear run-time complexity) */
	std::make_heap(Q.begin(), Q.end());

	while (Q.empty() == false)
	{
		std::cout << Q.front() << " ";

		/*
		 * swap the root and the rightmost array element, then
		 * "bubble down" the element placed at the root
		 */
		std::pop_heap(Q.begin(), Q.end());

		/* remove the last array element (previous root) */
		Q.pop_back();
	}
	std::cout << "\n";

	return 0;
}

Notice how we arranged the array elements into a valid heap in one operation instead of pushing one element at a time as we did before. This is the only difference between the example above and our very first example. The generated output is then:

4 3 2 1