How to Use STL Heap Algorithms in C++

1. Use the std::make_heap Function to Convert a Range Into a Heap
2. Use the std::sort_heap Function to Sort a Heap Range
3. Use the std::pop_heap Function to Remove the Next Element in the Heap

This article will demonstrate how to utilize STL heap algorithms in C++.

Use the std::make_heap Function to Convert a Range Into a Heap

The std::make_heap function is provided under the STL algorithms, and it can be used to construct a binary heap data structure from the given range. Generally, a heap data structure is tree-based, and the two common types are known as the max heap and min heap.

In a max heap, for any child node, the key from its parent node is greater than or equal to the child’s key. On the other hand, the key of the parent is less than equal to the child’s key. Now, the heap structure constructed with the make_heap function is a binary heap similar to a binary tree data structure. Note that heaps are efficient for element insertion and removal operations, which can be performed in logarithmic time.

The following example demonstrates the transformation of the std::vector process into a heap, and then the contents are printed using the usual printVector function. Note that the order of the elements is slightly mysterious. In fact, you can read them as the binary tree structure where the first element is the root key value.

Since there are only two children at maximum for every node in a binary tree, the 82 and 39 follow the root as the children. The next two elements are the children nodes of 82, and the other two are positioned under 39. This hierarchy satisfies the max heap property that the parent element has the greater than or equal key than its children.

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

using std::cout;
using std::endl;
using std::string;
using std::vector;

template <typename T>
void printVector(const vector<T> &vec) {
  for (auto &i : vec) {
    cout << i << "; ";
  }
  cout << endl;
}

int main() {
  vector<int> vec1{11, 82, 39, 72, 51, 32, 91};
  cout << "vec1 original:  ";
  printVector(vec1);

  std::make_heap(vec1.begin(), vec1.end());
  cout << "vec1 make_heap: ";
  printVector(vec1);

  return EXIT_SUCCESS;
}

Output:

vec1 original:  11; 82; 39; 72; 51; 32; 91;
vec1 make_heap: 91; 82; 39; 72; 51; 32; 11;

Use the std::sort_heap Function to Sort a Heap Range

You can utilize the std::sort_heap function to sort the previously converted range using the std::make_heap function. The simple overload of the std::sort_heap function, which takes only two iterator arguments, will sort the rang into ascending order. The other overload of the function can accept the third argument of comparison function with the following signature: bool cmp(const Type1 &a, const Type2 &b);. After the range is sorted, it no longer has the heap property.

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

using std::cout;
using std::endl;
using std::string;
using std::vector;

template <typename T>
void printVector(const vector<T> &vec) {
  for (auto &i : vec) {
    cout << i << "; ";
  }
  cout << endl;
}

int main() {
  vector<int> vec1{11, 82, 39, 72, 51, 32, 91};

  std::make_heap(vec1.begin(), vec1.end());
  printVector(vec1);

  std::sort_heap(vec1.begin(), vec1.end());
  printVector(vec1);

  return EXIT_SUCCESS;
}

Output:

91; 82; 39; 72; 51; 32; 11;
11; 32; 39; 51; 72; 82; 91;

Use the std::pop_heap Function to Remove the Next Element in the Heap

Heap structures usually support fast element insertion and removal operations. The std::push_heap and std::pop_heap functions conduct these operations for the heap range correspondingly. When the std::push_heap command is called on the heap range, its first element is swapped with the last position, and a new heap is constructed with the remaining elements. Note that the heap is constructed as a max heap by default parameters. One can pass an optional comparison function as the third argument to modify the heap hierarchy accordingly.

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

using std::cout;
using std::endl;
using std::string;
using std::vector;

template <typename T>
void printVector(const vector<T> &vec) {
  for (auto &i : vec) {
    cout << i << "; ";
  }
  cout << endl;
}

int main() {
  vector<int> vec1{11, 82, 39, 72, 51, 32, 91};

  std::make_heap(vec1.begin(), vec1.end());
  printVector(vec1);

  std::pop_heap(vec1.begin(), vec1.end());
  printVector(vec1);

  return EXIT_SUCCESS;
}

Output:

91; 82; 39; 72; 51; 32; 11;
82; 72; 39; 11; 51; 32; 91;