Previous fileTop of DocumentContentsIndex pageNext file
Apache C++ Standard Library User's Guide

14.7 heap Operations

A heap is a binary tree in which every node is larger than the values associated with either child. A heap and a binary tree, for that matter, can be very efficiently stored in a vector, by placing the children of node i in positions 2 * i + 1 and 2 * i + 2.

Using this encoding, the largest value in the heap is always located in the initial position, and can therefore be very efficiently retrieved. In addition, efficient logarithmic algorithms exist that permit a new element to be added to a heap and the largest element removed from a heap. For these reasons, a heap is a natural representation for the priority queue datatype, described in Chapter 11.

The default operator is the less-than operator < appropriate to the element type. If desired, an alternative operator can be specified. For example, by using the greater-than operator >, one can construct a heap that locates the smallest element in the first location, instead of the largest.

The algorithm std::make_heap() takes a range, specified by random access iterators, and converts it into a heap. The number of steps required is a linear function of the number of elements in the range.

To add a new element to a heap, insert it at the end of a range using the std::push_back() member function of a vector or deque, for example, and invoke the algorithm std::push_heap(). The std::push_heap() algorithm restores the heap property, performing at most a logarithmic number of operations.

The algorithm std::pop_heap() swaps the first and final elements in a range, and restores to a heap the collection without the final element. The largest value of the original collection is therefore still available as the last element in the range. It can be accessed using the back() member function in a vector, for example, and removed using the pop_back() member function. At the same time, the remainder of the collection continues to have the heap property. The std::pop_heap() algorithm performs at most a logarithmic number of operations.

Finally, the algorithm std::sort_heap() converts a heap into an ordered or sorted collection. Note that a sorted collection is still a heap, although the reverse is not the case.


NOTE -- An ordered collection is a heap, but a heap need not necessarily be an ordered collection. In fact, a heap can be constructed in a sequence much more quickly than the sequence can be sorted.

The sort is performed using approximately N log N operations, where N represents the number of elements in the range. The std::sort_heap() algorithm is not stable. Equal elements are not guaranteed to retain their relative pre-sort order.

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



Previous fileTop of DocumentContentsIndex pageNext file