make_heap() in C++ STL

The make heap() is used to create a heap from a set of given values. A heap is a tree type of data structure made up of a complete binary tree. The make_heap() is an in-built function provided by STL. Heaps are divided into two categories:

1. Max Heap : In max heap, the value of the parent node is greater than the values of its child nodes, this applies to all the nodes in the heap. This demonstrates that the root node is the node in the heap with the highest value.
2. Min Heap : In min heap, the value of the parent node is smaller than the values of its child nodes, this applies to all the nodes in the heap. This demonstrates that the root node is the node in the heap with the smallest value.

So, depending on the heap (max heap/ min heap) we can get the highest/ smallest value in O(1) time. We must include the header “algorithm” to use the make_heap().

Implementation of make_heap() in C++ STL

We have two types of implementations. Both are discussed below in C++ using STL.

1. Template : void make_heap(RandomAccessIterator First, RandomAccessIterator Last)
   First denotes the pointer of the starting element of the sequence and Last denotes the pointer to the next address of the last element of the sequence. Here sequence represents the collection of elements that has to be converted into a heap.

   #include <iostream>
   #include <vector> // for using vectors
   #include <algorithm> // for using make_heap()
   using namespace std;
   int main()
   {
        // defining a vector
        vector<int> v = { 12, 3, 15, 9, 5 };
        // Since we have a sequence of elements
        // we can use make heap function to convert
        // into a heap
        make_heap(v.begin(), v.end());
        // Normal make_heap implements a max heap
        // The root element must be the highest element
        cout<<"The maximum element is : "<<v.front();
        return 0;
   }

   Output :

   The maximum element is : 15

2. Template : void make_heap(RandomAccessIterator First, RandomAccessIterator Last, comparator)
   First denotes the pointer of the starting element of the sequence, Last denotes the pointer to the next address of the last element of the sequence and comparator function takes two arguments and returns either true/ false by comparing the arguments. Here sequence represents the collection of elements that has to be converted into a heap.

   #include <iostream>
   #include <vector> // for using vectors
   #include <algorithm> // for using make_heap()
   using namespace std;
   // Comparator function must be defined to
   // implement a min heap
   struct bigger{
        bool operator()(const int &x, const int &y) const{
             return x>y;
        }
   };
   int main()
   {
        // defining a vector
        vector<int> v = { 12, 3, 15, 9, 5 };
        // Converting into min heap
        make_heap(v.begin(), v.end(), bigger());
        // using the comparator function we made min heap
        // The root element must be the smallest one
        cout<<"The minimum element is : "<<v.front();
        return 0;
   }

   Output :

   The minimum element is : 3