push_heap

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

原型

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

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

说明

两个版本的push_heap它们定义如何判定一个元素是否小于另一个元素的方式不同。第一个版本使用operator<比较对象，而第二个版本使用 函数对象comp比较对象。第一个版本的先验条件是is_heap(first, last)为true，第二个版本的先验条件是is_heap(first, last, comp)为true.

定义

类型需求

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

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

前提条件

• [first, last)是一个有效范围。
• [first, last - 1)是一个有效范围。即，[first, last)是非空的。
• [first, last - 1)是堆。即，is_heap(first, last - 1)为true.

• [first, last)是一个有效范围。
• [first, last - 1)是一个有效范围。即，[first, last)是非空的。
• [first, last)是堆。即，is_heap(first, last - 1, comp)为true.

复杂性

示例

int main()
{
  int A[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };

  make_heap(A, A + 9);
  cout << "[A, A + 9)  = ";
  copy(A, A + 9, ostream_iterator<int>(cout, " "));
  
  push_heap(A, A + 10);
  cout << endl << "[A, A + 10) = ";
  copy(A, A + 10, ostream_iterator<int>(cout, " "));
  cout << endl;
}

输出是

[A, A + 9)  = 8 7 6 3 4 5 2 1 0 
[A, A + 10) = 9 8 6 3 7 5 2 1 0 4 

注释

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

另请参阅