beautypg.com

HP Integrity NonStop H-Series User Manual

Page 195

background image

performs at most a logarithmic number of operations.

void pop_heap (RandomAccessIterator first,
RandomAccessIterator last [, Compare ]);

Finally, the algorithm sort_heap() converts a heap into a ordered (sorted) collection. Note that a
sorted collection is still a heap, although the reverse is not the case. The sort is performed using
approximately n log n operations, where n represents the number of elements in the range. The
sort_heap() algorithm is not stable.

void sort_heap (RandomAccessIterator first,
RandomAccessIterator last [, Compare ]);

Here is an example program that illustrates the use of these functions.

void heap_example ()
// illustrate the use of the heap algorithms
{
// make a heap of 15 random integers
vector aVec(15);
generate (aVec.begin(), aVec.end(), randomValue);
make_heap (aVec.begin(), aVec.end());
cout << "Largest value " << aVec.front() << endl;

// remove largest and reheap
pop_heap (aVec.begin(), aVec.end());
aVec.pop_back();

// add a 97 to the heap
aVec.push_back (97);
push_heap (aVec.begin(), aVec.end());

// finally, make into a sorted collection
sort_heap (aVec.begin(), aVec.end());
}

This manual is related to the following products: