.\" ident @(#)make_heap.3 .\" Standard Template Library .\" $$RW_INSERT_HEADER "slyrs.man" .TH make_heap 3C++ "02 Apr 1998" "Rogue Wave Software" "-" .ce2 Standard C++ Library Copyright 1998, Rogue Wave Software, Inc. .SH NAME \f2make_heap\fP \ - Creates a heap. .SH SYNOPSIS .br #include .br template .RE .RS 1 void .RE .RS 2 make_heap(RandomAccessIterator first, .RE .RS 11 RandomAccessIterator last); .RE .RS 0 .br template .RE .RS 1 void .RE .RS 2 make_heap(RandomAccessIterator first, .RE .RS 11 RandomAccessIterator last, Compare comp); .SH DESCRIPTION A heap is a particular organization of elements in a range between two random access iterators\f2 [a, b)\fP. Its two key properties are: .HP .5i 1. \f2*a\fP is the largest element in the range. .HP .5i 2. \f2*a\fP may be removed by the pop_heap algorithm, or a new element can be added by the push_heap algorithm, in \f2O(logN)\fP time. .HP 0 These properties make heaps useful as priority queues. The heap algorithms use less than (\f2operator<\fP) 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 \f2[first, last)\fP into a heap using less than (\f2operator<\fP) to perform comparisons. The second version uses the comparison operator \f2comp\fP to perform the comparisons. Since the only requirements for a heap are the two listed above, \f2make_heap\fP is not required to do anything within the range \f2(first, last - 1)\fP. .SH COMPLEXITY This algorithm makes at most \f23 * (last - first)\fP comparisons. .SH EXAMPLE .RE .RS 0 // .br // heap_ops.cpp .br // .RE .RS 1 #include .br #include .br #include .RE .RS 0 using namespace std; .br .br int main(void) .RE .RS 1 { .RE .RS 2 int d1[4] = {1,2,3,4}; .br int d2[4] = {1,3,2,4}; .RE .RS 0 .RE .RS 3 // Set up two vectors .RE .RS 2 vector v1(d1,d1 + 4), v2(d2,d2 + 4); .RE .RS 0 .RE .RS 3 // Make heaps .br make_heap(v1.begin(),v1.end()); .br make_heap(v2.begin(),v2.end(),less()); .br // v1 = (4,x,y,z) and v2 = (4,x,y,z) .br // Note that x, y and z represent the remaining .br // values in the container (other than 4). .br // The definition of the heap and heap operations .br // does not require any particular ordering .br // of these values. .RE .RS 0 .RE .RS 3 // Copy both vectors to cout .RE .RS 2 ostream_iterator out(cout," "); .br copy(v1.begin(),v1.end(),out); .br cout << endl; .br copy(v2.begin(),v2.end(),out); .br cout << endl; .RE .RS 0 .RE .RS 3 // Now let's pop .RE .RS 2 pop_heap(v1.begin(),v1.end()); .br pop_heap(v2.begin(),v2.end(),less()); .RE .RS 3 // v1 = (3,x,y,4) and v2 = (3,x,y,4) .RE .RS 0 .RE .RS 3 // Copy both vectors to cout .RE .RS 2 copy(v1.begin(),v1.end(),out); .br cout << endl; .br copy(v2.begin(),v2.end(),out); .br cout << endl; .RE .RS 3 .br // And push .RE .RS 2 push_heap(v1.begin(),v1.end()); .br push_heap(v2.begin(),v2.end(),less()); .RE .RS 3 // v1 = (4,x,y,z) and v2 = (4,x,y,z) .RE .RS 0 .RE .RS 3 // Copy both vectors to cout .RE .RS 2 copy(v1.begin(),v1.end(),out); .br cout << endl; .br copy(v2.begin(),v2.end(),out); .br cout << endl; .RE .RS 0 .RE .RS 3 // Now sort those heaps .RE .RS 2 sort_heap(v1.begin(),v1.end()); .br sort_heap(v2.begin(),v2.end(),less()); .RE .RS 3 // v1 = v2 = (1,2,3,4) .RE .RS 6 .RE .RS 3 // Copy both vectors to cout .RE .RS 2 copy(v1.begin(),v1.end(),out); .br cout << endl; .br copy(v2.begin(),v2.end(),out); .br cout << endl; .RE .RS 0 .RE .RS 2 return 0; .RE .RS 1 } .br .RE .RS 0 Program Output .RE .RS 0 .br 4 2 3 1 .br 4 3 2 1 .br 3 2 1 4 .br 3 1 2 4 .br 4 3 1 2 .br 4 3 2 1 .br 1 2 3 4 .br 1 2 3 4 .SH WARNINGS If your compiler does not support default template parameters, then you always need to supply the \f2Allocator\fP template argument. For instance, you have to write: \f2vector >\fP instead of: \f2vector\fP If your compiler does not support namespaces, then you do not need the using declaration for \f2std\fP. .SH SEE ALSO pop_heap, push_heap and sort_heap