pop_heap

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

原型

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

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

描述

比较对象pop_heap的第一个版本的后续条件是is_heap(first, last-1)为true且*(last - 1)是从堆中移除的元素。第二个版本的后续条件是is_heap(first, last-1, comp)为true且*(last - 1)是从堆中移除的元素。 [2]

定义

对类型的要求

• RandomAccessIterator是 随机访问迭代器 的模型。
• RandomAccessIterator是可变的。
• RandomAccessIterator的值类型是 Less-Than Comparable 的模型。
• 根据 Less-Than Comparable 要求中定义的，对RandomAccessIterator的值类型的对象的排序是一种严格弱排序。

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

先决条件

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

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

复杂度

示例

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

  make_heap(A, A+N);
  cout << "Before pop: ";
  copy(A, A+N, ostream_iterator<int>(cout, " "));

  pop_heap(A, A+N);
  cout << endl << "After pop: ";
  copy(A, A+N-1, ostream_iterator<int>(cout, " "));
  cout << endl << "A[N-1] = " << A[N-1] << endl;
}

输出为

Before pop: 6 5 3 4 2 1 
After pop: 5 4 3 1 2 
A[N-1] = 6

注意

[1] 堆是一种使用 Random Access Iterators[f, l)对一组元素排序的特定方式。堆之所以有用（尤其是用于排序或作为优先级队列），是因为它们满足两个重要的条件。首先，*f是在堆中最大的元素。其次，可以使用push_heap（将元素添加到堆中）或删除*f，以对数时间进行比较。

[2] Pop_heap从堆中删除最大的元素，并缩小堆。这意味着如果你总是在调用pop_heap直到堆中仅剩一个元素，最终将获得堆原先所在位置的排序范围。事实上，这是sort_heap实现的方式。

请参见