|
sort_heap
function template
<algorithm>
template <class RandomAccessIterator>
void sort_heap ( RandomAccessIterator first, RandomAccessIterator last );
template <class RandomAccessIterator, class Compare>
void sort_heap ( RandomAccessIterator first, RandomAccessIterator last,
Compare comp );
Sort elements of heap
Rearranges the elements in the heap range [first,last) in such a way that they form a sorted range. The comparisons are perfomed using operator< for the first version, and comp for the second.
The range loses its heap properties.
Parameters
- first, last
- Random-Access iterators to the initial and final positions of the heap range to be sorted. The range used is [first,last), which contains all the elements between first and last, including the element pointed by first but not the element pointed by last.
- comp
- Comparison function object that, taking two values of the same type than those contained in the range, returns true if the first argument goes before the second argument in the specific strict weak ordering it defines, and false otherwise.
Return value
none
Example
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
// range heap example
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main () {
int myints[] = {10,20,30,5,15};
vector<int> v(myints,myints+5);
vector<int>::iterator it;
make_heap (v.begin(),v.end());
cout << "initial max heap : " << v.front() << endl;
pop_heap (v.begin(),v.end()); v.pop_back();
cout << "max heap after pop : " << v.front() << endl;
v.push_back(99); push_heap (v.begin(),v.end());
cout << "max heap after push: " << v.front() << endl;
sort_heap (v.begin(),v.end());
cout << "final sorted range :";
for (unsigned i=0; i<v.size(); i++) cout << " " << v[i];
cout << endl;
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
|
Complexity
At most, NlogN comparisons, where N is (last-first).
See also
| make_heap | Make heap from range (function template) |
| push_heap | Push element into heap range (function template) |
| pop_heap | Pop element from heap range (function template) |
| reverse | Reverse range (function template) |
|