Previous fileTop of DocumentContentsIndex pageNext file
Apache C++ Standard Library Reference Guide


Library:  Algorithms


Local Index

No Entries


Algorithm that moves the largest element off the heap


#include <algorithm>

namespace std {
template <class RandomAccessIterator>
  pop_heap(RandomAccessIterator start,
           RandomAccessIterator finish);

template <class RandomAccessIterator, class Compare>
  pop_heap(RandomAccessIterator start,
           RandomAccessIterator finish, Compare comp);


A heap is a particular organization of elements in a range between two random access iterators [a, b). Its two key properties are:

  1. *a is the largest element in the range.

  2. *a may be removed by the pop_heap() algorithm or a new element may be added by the pop_heap() algorithm, in O(log(N)) time.

These properties make heaps useful as priority queues.

The pop_heap() algorithm uses operator<() as the default comparison. An alternate comparison operator can be specified to the second overload of the function template.

The pop_heap() algorithm can be used as part of an operation to remove the largest element from a heap. It assumes that the range [start, finish) is a valid heap (in other words, that start is the largest element in the heap or the first element based on the alternate comparison operator). It then swaps the value in the location start with the value in the location finish - 1 and makes the range [start, finish - 1) back into a heap.


pop_heap() performs at most 2 * log(finish - start) comparisons.


See Also

make_heap(), push_heap(), sort_heap()

Standards Conformance

ISO/IEC 14882:1998 -- International Standard for Information Systems -- Programming Language C++, Section

Previous fileTop of DocumentContentsIndex pageNext file