is_heap


类别: 算法	组件类型: 函数

原型

Is_heap是一个重载名称; 实际上有两个 is_heap 函数。

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)

描述

Is_heap返回true如果范围[first, last)是一个堆 [1]，并且false否则。这两个版本在定义一个元素是否小于另一个元素方面有所不同：第一个版本使用operator<比较对象，第二个版本使用函数对象comp.

定义

在标准头文件 algorithm 和非标准向后兼容头文件 algo.h 中定义。此函数是 SGI 扩展；它不是 C++ 标准的一部分。

类型要求

对于第一个版本

RandomAccessIterator是随机访问迭代器的模型。
RandomAccessIterator的值类型是小于可比较的模型。
对RandomAccessIterator的值类型的对象的排序是严格弱排序，如小于可比较要求中定义的那样。

对于第二个版本

RandomAccessIterator是随机访问迭代器的模型。
StrictWeakOrdering是严格弱排序的模型。
RandomAccessIterator的值类型可以转换为StrictWeakOrdering的参数类型。

先决条件

[first, last)是一个有效范围。

复杂度

线性。如果[first, last)是一个空范围，则为零比较，否则最多为(last - first) - 1次比较。

示例

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));

注释

[1] 堆是随机访问迭代器范围中元素排序的一种特定方式[f, l). 堆之所以有用（特别是对于排序或作为优先级队列）是因为它们满足两个重要的属性。首先，*f是堆中最大的元素。其次，可以在对数时间内将元素添加到堆中（使用push_heap），或删除*f。在内部，堆是一棵树，以顺序范围表示。构造树的方式使得每个节点都小于或等于其父节点。

另请参阅

make_heap, push_heap, pop_heap, sort_heap