C++

参考

<algorithm>

函数模板
<algorithm>

std::sort_heap

默认 (1)
template <class RandomAccessIterator>  void sort_heap (RandomAccessIterator first, RandomAccessIterator last);
自定义 (2)
template <class RandomAccessIterator, class Compare>  void sort_heap (RandomAccessIterator first, RandomAccessIterator last,                  Compare comp);
对堆排序
将堆范围 [first,last) 中的元素按升序排序。

第一个版本使用 operator< 比较元素，第二个版本使用 comp 比较元素。后者应与用于构造堆的比较器相同。

此范围将失去其作为堆的属性。

参数

first, last
随机访问迭代器，指向要排序的堆范围的初始位置和末尾位置。使用的范围是 [first,last)，它包含 first 指向的元素和 last 指向的元素之间的所有元素，但不包含 last 指向的元素。
comp
二元函数，接受范围中的两个元素作为参数，并返回一个可转换为 bool 的值。返回的值表示传递给第一个参数的元素是否被认为在它定义的特定严格弱序中排在第二个元素之前。
除非 [first,last) 是一个单元素的堆，否则此参数应与用于构造堆的参数相同。
该函数不得修改其任何参数。
这可以是函数指针或函数对象。

返回值

无

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
 
// range heap example
#include <iostream>     // std::cout
#include <algorithm>    // std::make_heap, std::pop_heap, std::push_heap, std::sort_heap
#include <vector>       // std::vector

int main () {
  int myints[] = {10,20,30,5,15};
  std::vector<int> v(myints,myints+5);

  std::make_heap (v.begin(),v.end());
  std::cout << "initial max heap   : " << v.front() << '\n';

  std::pop_heap (v.begin(),v.end()); v.pop_back();
  std::cout << "max heap after pop : " << v.front() << '\n';

  v.push_back(99); std::push_heap (v.begin(),v.end());
  std::cout << "max heap after push: " << v.front() << '\n';

  std::sort_heap (v.begin(),v.end());

  std::cout << "final sorted range :";
  for (unsigned i=0; i<v.size(); i++)
    std::cout << ' ' << v[i];

  std::cout << '\n';

  return 0;
}

输出
initial max heap   : 30
max heap after pop : 20
max heap after push: 99
final sorted range : 5 10 15 20 99


复杂度

线性对数复杂度，相对于 first 和 last 之间的距离：进行至多 N*log(N) 次（其中 N 是此距离）元素比较，以及至多同等次数的元素交换（或移动）。

数据竞争

范围[first,last)内的对象将被修改。

异常

如果任何元素比较、元素交换（或移动）或迭代器操作抛出异常，则会抛出异常。
请注意，无效参数会导致未定义行为。

另见

make_heap
从范围创建堆 （函数模板）
push_heap
将元素推入堆范围 （函数模板）
pop_heap
从堆范围中弹出元素 （函数模板）
reverse
反转范围 （函数模板）