C++ In a Nutshell

Name

make_heap function template — Reorders a range to convert it into a heap

Synopsis

template<typename RandIter> 
  void make_heap(RandIter first, RandIter last);
template<typename RandIter, typename Compare>
  void make_heap(RandIter first, RandIter last, Compare comp);

The make_heap function template reorders the elements in the range [first, last) to form a heap in place.

The first form compares values using the < operator. The second form calls comp(*iter, value).

Heap Data Structure

A heap is a data structure that is ideally suited for implementing priority queues. C++ defines a range as a heap if two properties are satisfied:

• The first element of the range is the largest, which strictly means that *first < *(first + n) is false for all n in [1, last - first).

• Adding or removing an element can be done in logarithmic time, and the result is still a heap.

The classic example of a heap is a binary tree, in which each node is greater than or equal to its children, but the relative order of the children is not specified. Thus, the root of the tree is the largest element in the entire tree.

Technical Notes

Postcondition: [first, last) is a heap.

Complexity is linear: at most, 3 × (last - first) comparisons are performed.

See Also

pop_heap function template, push_heap function template, sort_heap function template, <queue>