Algorithm
Creates a heap.
#include <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);
A heap is a particular organization of elements in a range between two random access iterators [a, b). Its two key properties are:
*a is the largest element in the range.
*a may be removed by the pop_heap algorithm, or a new element can be added by the push_heap algorithm, in O(logN) time.
These properties make heaps useful as priority queues.
The heap algorithms use less than (operator<) as the default comparison. In all of the algorithms, an alternate comparison operator can be specified.
The first version of the make_heap algorithm arranges the elements in the range [first, last) into a heap using less than (operator<) to perform comparisons. The second version uses the comparison operator comp to perform the comparisons. Since the only requirements for a heap are the two listed above, make_heap is not required to do anything within the range (first, last - 1).
This algorithm makes at most 3 * (last - first) comparisons.
// // heap_ops.cpp // #include <algorithm> #include <vector> #include <iostream.h> int main(void) { int d1[4] = {1,2,3,4}; int d2[4] = {1,3,2,4}; // Set up two vectors vector<int> v1(d1,d1 + 4), v2(d2,d2 + 4); // Make heaps make_heap(v1.begin(),v1.end()); make_heap(v2.begin(),v2.end(),less<int>()); // v1 = (4,x,y,z) and v2 = (4,x,y,z) // Note that x, y and z represent the remaining // values in the container (other than 4). // The definition of the heap and heap operations // does not require any particular ordering // of these values. // Copy both vectors to cout ostream_iterator<int> out(cout," "); copy(v1.begin(),v1.end(),out); cout << endl; copy(v2.begin(),v2.end(),out); cout << endl; // Now let's pop pop_heap(v1.begin(),v1.end()); pop_heap(v2.begin(),v2.end(),less<int>()); // v1 = (3,x,y,4) and v2 = (3,x,y,4) // Copy both vectors to cout copy(v1.begin(),v1.end(),out); cout << endl; copy(v2.begin(),v2.end(),out); cout << endl; // And push push_heap(v1.begin(),v1.end()); push_heap(v2.begin(),v2.end(),less<int>()); // v1 = (4,x,y,z) and v2 = (4,x,y,z) // Copy both vectors to cout copy(v1.begin(),v1.end(),out); cout << endl; copy(v2.begin(),v2.end(),out); cout << endl; // Now sort those heaps sort_heap(v1.begin(),v1.end()); sort_heap(v2.begin(),v2.end(),less<int>()); // v1 = v2 = (1,2,3,4) // Copy both vectors to cout copy(v1.begin(),v1.end(),out); cout << endl; copy(v2.begin(),v2.end(),out); cout << endl; return 0; } Output : 4 2 3 1 4 3 2 1 3 2 1 4 3 1 2 4 4 3 1 2 4 3 2 1 1 2 3 4 1 2 3 4
If your compiler does not support default template parameters then you need to always supply the Allocator template argument. For instance you'll have to write:
vector<int,allocator>
instead of:
vector<int>
pop_heap, push_heap, and sort_heap