|
make_heap
function template
<algorithm>
template <class RandomAccessIterator>
void make_heap ( RandomAccessIterator first, RandomAccessIterator last );
template <class RandomAccessIterator, class Compare>
void make_heap ( RandomAccessIterator first, RandomAccessIterator last,
Compare comp );
Make heap from range
Rearranges the elements in the range [first,last) in such a way that they form a heap. In order to rearrange these elements, the function performs comparisons using operator< for the first version, and comp for the second.
Internally, a heap is a tree where each node links to values not greater than its own value. In heaps generated by make_heap, the specific position of an element in the tree rather than being determined by memory-consuming links is determined by its absolute position in the sequence, with *first being always the highest value in the heap.
You can add or remove elements from a heap in logarithmic time by using the functions push_heap and pop_heap. These functions preserve the heap properties of the range passed to them.
Parameters
- first, last
- Random-Access iterators to the initial and final positions of the sequence to be transformed into a heap. 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, (3*(last-first)) comparisons.
See also
| push_heap | Push element into heap range (function template) |
| pop_heap | Pop element from heap range (function template) |
| sort_heap | Sort elements of heap (function template) |
| reverse | Reverse range (function template) |
|