make_heap

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

原型

template <class RandomAccessIterator>
void make_heap(RandomAccessIterator first, RandomAccessIterator last);

template <class RandomAccessIterator, class StrictWeakOrdering>
void make_heap(RandomAccessIterator first, RandomAccessIterator last,
               StrictWeakOrdering comp);

说明

两个版本的make_heap如何定义一个元素是否小于另一个元素，这一点上有差异。第一个版本使用运算符<比较对象，并且第二个版本使用 函数对象comp比较对象。在第一个版本中，后置条件是is_heap(first, last)是true，并且在第二个版本中，后置条件是is_heap(first, last, comp)是true.

定义

对类型的要求

• RandomAccessIterator是 随机访问迭代器 的模型。
• RandomAccessIterator是可变的。
• RandomAccessIterator其值类型为 LessThan Comparable 模型。
• 其值类型的对象必须具有排序，即RandomAccessIterator针对它的值类型的对象排序，在 LessThan Comparable 要求中定义为“严格弱排序”。

• RandomAccessIterator是 随机访问迭代器 的模型。
• RandomAccessIterator是可变的。
• StrictWeakOrdering是 Strict Weak Ordering 模型。
• RandomAccessIterator的值类型可转换为StrictWeakOrdering的参数类型。

前提条件

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

复杂性

示例

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

  make_heap(A, A+N);
  copy(A, A+N, ostream_iterator<int>(cout, " "));
  cout << endl;

  sort_heap(A, A+N);
  copy(A, A+N, ostream_iterator<int>(cout, " "));
  cout << endl;
}

备注

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

另请参阅