C++ Algorithm make_heap()

C++ Algorithm make_heap() function is used to rearrange the elements in the range [first, last) in such a way that they form a heap.

Elements are compared using operator < for the first version or using the given binary comparison function comp for the second version.

Syntax

  default (1)         template <class RandomAccessIterator>                        void make_heap (RandomAccessIterator first, RandomAccessIterator last);    custom (2)   template <class RandomAccessIterator, class Compare>                        void make_heap (RandomAccessIterator first, RandomAccessIterator last,                                                                              Compare comp );  

Parameter

first: A random access iterator pointing to the first element in the range to be converted into a heap.

last: A random access iterator pointing to the past last element in the range to be converted into a heap.

comp: A user defined binary predicate function that accepts two arguments and returns true if the two arguments are in order and false otherwise. It follows the strict weak ordering to order the elements.

Return value

None

Complexity

Complexity is up to linear in three times the distance between first and last: compares elements and potentially swaps (or moves) them until rearranges as a longer heap.

Data races

Some of the objects in the range [first, last) are modified.

Exceptions

This function throws an exception if any of element comparisons, the element swaps (or moves) or an operation on iterator throws an exception.

Note: The invalid parameters cause an undefined behavior.

Example 1

Let’s see the simple example to demonstrate the use of make_heap():

  #include <iostream>  #include <vector>  #include <algorithm>    using namespace std;    int main()  {    vector<int> v = {2, 1, 4, 3};      make_heap(v.begin(), v.end());      for_each(v.begin(), v.end(), [](int x) {      cout << x << endl;    });        return 0;  }  

Output:

4  3  2  1

Example 2

Let’s see another simple example:

  #include <iostream>     // std::cout  #include <algorithm>    // std::make_heap, std::pop_heap, std::push_heap, std::sort_heap  #include <vector>       // std::vector    using namespace std;    int main () {    int myints[] = {20,10,30,5,13};    vector<int> v(myints,myints+5);      make_heap (v.begin(),v.end());    cout << “initial max heap   : ” << v.front() << ‘n’;      pop_heap (v.begin(),v.end()); v.pop_back();    cout << “max heap after pop : ” << v.front() << ‘n’;      v.push_back(99); push_heap (v.begin(),v.end());    cout << “max heap after push: ” << v.front() << ‘n’;      sort_heap (v.begin(),v.end());      cout << “final sorted range :”;    for (unsigned i=0; i<v.size(); i++)      cout << ‘ ‘ << v[i];      cout << ‘n’;      return 0;  }  

Output:

initial max heap   : 30  max heap after pop : 20  max heap after push: 99  final sorted range : 5 10 13 20 99

Example 3

Let’s see another simple example to convert an arbitrary vector of integers into a heap using comparison function:

  #include <iostream>  #include <vector>  #include <algorithm>  #include <functional>     using namespace std;     int main()  {    int a[] = {15, 27, 16, 20, 30, 100, 3, 16, 7};    vector<int> v(a, a+9);      cout <<“nHere are the values in the vector:n”;    for (vector<int>::size_type i=0; i<v.size(); i++)      cout <<v.at(i)<<” “;       cout <<“nNow we make these values into a (minimum) heap.”;    make_heap(v.begin(), v.end(), greater<int>());       cout <<“nHere are the revised contents of the vector:n”;    for (vector<int>::size_type i=0; i<v.size(); i++)      cout <<v.at(i)<<” “;       return 0;  }  

Output:

Here are the values in the vector:  15 27 16 20 30 100 3 16 7   Now we make these values into a (minimum) heap.  Here are the revised contents of the vector:  3 7 15 16 30 100 16 27 20

Example 4

Let’s see a simple example:

  #include <iostream>  #include <algorithm>  #include <vector>    using namespace std;     int main()  {      vector<int> v { 3, 1, 4, 1, 5, 9 };         cout << “initially, v: “;      for (auto i : v) cout << i << ‘ ‘;      cout << ‘n’;         make_heap(v.begin(), v.end());         cout << “after make_heap, v: “;      for (auto i : v) cout << i << ‘ ‘;      cout << ‘n’;         pop_heap(v.begin(), v.end());      auto largest = v.back();      v.pop_back();      cout << “largest element: ” << largest << ‘n’;         std::cout << “after removing the largest element, v: “;      for (auto i : v) cout << i << ‘ ‘;      cout << ‘n’;    return 0;  }  

Output:

initially, v: 3 1 4 1 5 9   after make_heap, v: 9 5 4 1 1 3   largest element: 9  after removing the largest element, v: 5 3 4 1 1

Next TopicC++ Algorithm

adjacent_find()algorithm any_of()beginners copy_if()copy()count_if()count()cpp equal()find_end()find_first_of()find_if_not() for_each()find_if()find()professionals tutorial

C++ algorithm make_heap() function

C++ Algorithm make_heap()

Syntax

Parameter

Return value

Complexity

Data races

Exceptions

Note: The invalid parameters cause an undefined behavior.

Example 1

Example 2

Example 3

Example 4

Underwriting of Shares

C++ Math abs() Functions

You may also like