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

push_heap()

Library:  Algorithms


Function

Local Index

No Entries

Summary

An algorithm that places a new element into a heap

Synopsis

#include <algorithm>

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

  template <class RandomAccessIterator, class Compare>
  void
  push_heap(RandomAccessIterator start,
            RandomAccessIterator finish, Compare comp);
}

Description

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 push_heap() algorithm, in O(logN) time.

These properties make heaps useful as priority queues.

The first overload of the push_heap() algorithm uses operator<() for comparison. The second overload uses the supplied binary predicate comp.

The push_heap() algorithm is used to add a new element to the heap. First, a new element for the heap is added to the end of a range. The push_heap() algorithm assumes that the range [start, finish - 1) is a valid heap. Then it properly positions the element in the location finish - 1 into its proper position in the heap, resulting in a heap over the range [start, finish).

Complexity

For push_heap() at most log(finish - start) comparisons are performed.

Example

See Also

make_heap(), pop_heap(), sort_heap()

Standards Conformance

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



Previous fileTop of DocumentContentsIndex pageNext file