Heap operations

Source code

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

• RandomAccessIterator must be a regular random access iterator .
• For the push_heap operation, Compare must be a function object type that provides int operator()(S, T), where S is the dereference type of \ RandomAccessIterator. For the remaining heap operations, Compare must be a function object type that provides int operator()(S, S), where S is the dereference type of \ RandomAccessIterator.

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:

1. The value of the iterator a is the largest element in the range.

2. The value of the iterator a may be removed by pop_heap, or a new element added by push_heap, in logarithmic time.

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.