# is_heap

Category: algorithms | Component type: function

### Prototype

`Is_heap` is an overloaded name; there are actually two is_heap functions.

    template <class RandomAccessIterator>
    bool is_heap(RandomAccessIterator first, RandomAccessIterator last);

    template <class RandomAccessIterator, class StrictWeakOrdering>
    inline bool is_heap(RandomAccessIterator first, RandomAccessIterator last,
                        StrictWeakOrdering comp)

### Description

`Is_heap` returns `true` if the range `[first, last)` is a heap [1], and `false` otherwise. The two versions differ in how they define whether one element is less than another: the first version compares objects using `operator<`, and the second compares objects using a function object `comp`.

### Definition

Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h. This function is an SGI extension; it is not part of the C++ standard.

### Requirements on types

For the first version:

- `RandomAccessIterator` is a model of Random Access Iterator.
- `RandomAccessIterator`'s value type is a model of LessThan Comparable.
- The ordering on objects of `RandomAccessIterator`'s value type is a strict weak ordering, as defined in the LessThan Comparable requirements.

For the second version:

- `RandomAccessIterator` is a model of Random Access Iterator.
- `StrictWeakOrdering` is a model of Strict Weak Ordering.
- `RandomAccessIterator`'s value type is convertible to `StrictWeakOrdering`'s argument type.

### Preconditions

- `[first, last)` is a valid range.

### Complexity

Linear. Zero comparisons if `[first, last)` is an empty range, otherwise at most `(last - first) - 1` comparisons.

### Example

    int A[] = {1, 2, 3, 4, 5, 6, 7};
    const int N = sizeof(A) / sizeof(int);

    assert(!is_heap(A, A+N));
    make_heap(A, A+N);
    assert(is_heap(A, A+N));

### Notes

[1] A heap is a particular way of ordering the elements in a range of Random Access Iterators `[f, l)`. The reason heaps are useful (especially for sorting, or as priority queues) is that they satisfy two important properties. First, `*f` is the largest element in the heap. Second, it is possible to add an element to a heap (using `push_heap`), or to remove `*f`, in logarithmic time. Internally, a heap is a tree represented as a sequential range. The tree is constructed so that that each node is less than or equal to its parent node.

### See also

`make_heap`, `push_heap`, `pop_heap`, `sort_heap`

Copyright © 1999 Silicon Graphics, Inc. All Rights Reserved. TrademarkInformation