Declaration
template <class RandomAccessIterator> inline void push_heap(RandomAccessIterator first, RandomAccessIterator last); template <class RandomAccessIterator, class Compare> inline void push_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp); template <class RandomAccessIterator> inline void pop_heap(RandomAccessIterator first, RandomAccessIterator last); template <class RandomAccessIterator, class Compare> inline void pop_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp); template <class RandomAccessIterator> inline void make_heap(RandomAccessIterator first, RandomAccessIterator last); template <class RandomAccessIterator, class Compare> inline void make_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp); template <class RandomAccessIterator> void sort_heap(RandomAccessIterator first, RandomAccessIterator last); template <class RandomAccessIterator, class Compare> void sort_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
Description The push_heap functions place the value that is in the last dereferencable location of the sequence into the heap represented by the range of size n, where n is one less than the size of the range [ first, last) , beginning at first. The result of push_heap is a range that is a heap that is the size of the range [ first, last) .
The pop_heap functions swaps the element whose value is stored in the iterator first in the heap with the element whose value is stored in the last dereferencable location of the range. The range of size n, where n is one less than the size of the range [ first, last) , is then adjusted to represent a valid heap.
The make_heap functions construct a heap in the range [ first, last) using the values in the range [ first, last) .
The sort_heap functions sort the elements that are stored in the heap represented in the range [ first, last) .
In the first function of each pair of functions, element comparisons are done using operator<, while in the second they are done using the function object comp .
Type requirements
Group Sorting and related operations
Time complexity Logarithmic for the push_heap and pop_heap functions, linear for the make_heap functions, and
for the sort_heap functions, where n is the size of the range [ first, last) .
The push_heap functions require at most
comparisons, the pop_heap functions require at most
comparisons.
The make_heap functions perform at most 3 * n comparisons.
The sort_heap functions perform at most comparisons.
Space complexity Constant.
Mutative? Yes.
Details Given a range [ a, b) , a heap has two key properties:
Example Select here to view the source code for the example.
Implementation Select here to view source code (Copyright (C) 1994, Hewlett-Packard Company) for this algorithm.