C++ Algorithm sort_heap()

C++ Algorithm sort_heap() function is used to converts a heap [first, last) into a sorted range in ascending order.

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 sort_heap (RandomAccessIterator first, RandomAccessIterator last);    custom (2)    template <class RandomAccessIterator, class Compare>                     void sort_heap (RandomAccessIterator first, RandomAccessIterator last,                                                 Compare comp);  

Parameter

first: A random access iterator pointing to the first element in the target heap.

last: A random access iterator pointing to the past last element in the target heap.

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

Return value

None

Complexity

Complexity is up to linearithmic in the distance between first and last: performs at most N*log (N) comparisons of elements and up to that many elements swaps or moves where N = last – first.

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 sort_heap() using default version:

  #include <iostream>  #include <vector>  #include <algorithm>     using namespace std;     int main()  {     int a[] = {11, 22, 36, 17, 3, 25, 1, 2, 7};    vector<int> v(a, a+9);       cout <<“nHere are the values in the heap:n”;    for (vector<int>::size_type i=0; i<v.size(); i++)      cout <<v.at(i)<<” “;       cout <<“nNow we sort these values into ascending order.”;    sort_heap(v.begin(), v.end());       cout <<“nHere is the result: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 heap:  11 22 36 17 3 25 1 2 7   Now we sort these values into ascending order.  Here is the result:  1 2 3 7 17 22 25 36 11

Example 2

Let’s see another simple example to demonstrate the use of sort_heap() using comparison function:

  #include <iostream>  #include <vector>  #include <algorithm>  #include <functional>     using namespace std;     int main()  {    int a[] = {11, 12, 15, 17, 13, 100, 36, 19};    vector<int> v(a, a+9);       cout <<“nHere are the values in the heap:n”;    for (vector<int>::size_type i=0; i<v.size(); i++)      cout <<v.at(i)<<” “;       cout <<“nNow we sort these values into descending order.”;    sort_heap(v.begin(), v.end(), greater<int>());       cout <<“nHere are the results: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 heap:  11 12 15 17 13 100 36 19 0   Now we sort these values into descending order.  Here are the results:  100 36 19 17 15 13 12 0 11

Example 3

Let’s see another simple example:

  #include <iostream>     // cout  #include <algorithm>    // make_heap, pop_heap, push_heap, sort_heap  #include <vector>       // vector    using namespace std;    int main () {    int myints[] = {10,20,30,5,15};    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); std::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 15 20 99

Example 4

Let’s see a simple example:

  #include <iostream>  #include <vector>  #include <algorithm>  #include <functional>  #include <iomanip>     using namespace std;      void print(const vector <int>& v)  {      vector <int>::const_iterator i;      for(i = v.begin(); i != v.end(); i++)      {          cout << *i << ” “;      }      cout << endl;  }     int main()  {      int arr[] = {10, 20, 40, 80, 160, 320};      vector<int> v(arr, arr + sizeof(arr) / sizeof(int));         cout << “Vector” << setw(4) << “: “;      print(v);      // default make_heap creates max-heap      make_heap(v.begin(), v.end());      cout << “Heap” << setw(6) << “: “;      print(v);      sort_heap(v.begin(), v.end());      cout << “Sorted” << setw(4) << “: “;      print(v);      sort_heap(v.begin(), v.end(), greater<int>());      cout << “Reverse” << setw(3) << “: “;      print(v);            return 0;  }  

Output:

Vector  : 10 20 40 80 160 320   Heap    : 320 160 40 80 20 10   Sorted  : 10 20 40 80 160 320   Reverse : 320 160 80 40 20 10

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 sort_heap() function

C++ Algorithm sort_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