sort_heap
Converts a heap into a sorted range.
template<class RandomAccessIterator>
void sort_heap(
RandomAccessIterator _First,
RandomAccessIterator _Last
);
template<class RandomAccessIterator, class Predicate>
void sort_heap(
RandomAccessIterator _First,
RandomAccessIterator _Last,
Predicate _Comp
);
Parameters
_First
A random-access iterator addressing the position of the first element in the target heap._Last
A random-access iterator addressing the position one past the final element in the target heap._Comp
User-defined predicate function object that defines sense in which one element is less than another. A binary predicate takes two arguments and returns true when satisfied and false when not satisfied.
Remarks
Heaps have two properties:
The first element is always the largest.
Elements may be added or removed in logarithmic time.
After the application if this algorithm, the range it was applied to is no longer a heap.
This is not a stable sort because the relative order of equivalent elements is not necessarily preserved.
Heaps are an ideal way to implement priority queues and they are used in the implementation of the Standard Template Library container adaptor priority_queue Class.
The range referenced must be valid; all pointers must be dereferenceable and within the sequence the last position is reachable from the first by incrementation.
The complexity is at most N log N, where N = (_Last – _First).
Example
// alg_sort_heap.cpp
// compile with: /EHsc
#include <vector>
#include <algorithm>
#include <functional>
#include <iostream>
int main( ) {
using namespace std;
vector <int> v1, v2;
vector <int>::iterator Iter1, Iter2;
int i;
for ( i = 1 ; i <= 9 ; i++ )
v1.push_back( i );
random_shuffle( v1.begin( ), v1.end( ) );
cout << "Vector v1 after random_shuffle is ( " ;
for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
cout << *Iter1 << " ";
cout << ")." << endl;
// Make v1 a heap
make_heap(v1.begin(), v1.end());
cout << "Vector v1 after first make_heap is ( " ;
for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
cout << *Iter1 << " ";
cout << ")." << endl;
// Sort heap v1 with default less-than ordering
sort_heap (v1.begin( ), v1.end( ) );
cout << "The heap v1 becomes the sorted range: ( " ;
for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
cout << *Iter1 << " ";
cout << ")." << endl;
// Make v1 a heap with greater than ordering
make_heap ( v1.begin( ), v1.end( ), greater<int>( ) );
cout << "The greater-than heaped version of v1 is\n ( " ;
for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
cout << *Iter1 << " ";
cout << ")." << endl;
sort_heap(v1.begin( ), v1.end( ), greater<int>( ) );
cout << "The greater-than heap v1 becomes the sorted range\n ( " ;
for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
cout << *Iter1 << " ";
cout << ")." << endl;
}
Sample Output
Vector v1 after random_shuffle is ( 9 2 7 3 1 6 8 4 5 ).
Vector v1 after first make_heap is ( 9 5 8 4 1 6 7 2 3 ).
The heap v1 becomes the sorted range: ( 1 2 3 4 5 6 7 8 9 ).
The greater-than heaped version of v1 is
( 1 2 3 4 5 6 7 8 9 ).
The greater-than heap v1 becomes the sorted range
( 9 8 7 6 5 4 3 2 1 ).
Requirements
Header: <algorithm>
Namespace: std