sort_heap

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

原型

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

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

描述

这两个版本sort_heap在如何定义一个元素小于另一个元素方面有所不同。第一个版本使用operator<比较对象，第二个版本使用 函数对象comp.

定义

类型要求

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

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

先决条件

• [first, last)是一个有效的范围。
• [first, last)是一个堆。也就是说，is_heap(first, last)是true.

• [first, last)是一个有效的范围。
• [first, last)是一个堆。也就是说，is_heap(first, last, comp)是true.

复杂度

示例

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，时间复杂度为对数级。在内部，堆是一棵表示为顺序范围的树。树的构建方式使得每个节点都小于或等于其父节点。

另请参阅