std::
sort_heap
函数模板 <algorithm>| default (1) | template <class RandomAccessIterator> void sort_heap (RandomAccessIterator first, RandomAccessIterator last); |
| custom (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之间的所有元素，包括first指向的元素，但不包括last指向的元素。
- comp
-
二元函数，接受范围内的两个元素作为参数，
并返回一个可转换为bool类型的值。
返回的值表示作为第一个参数传递的元素是否被认为在它定义的特定严格弱排序中位于第二个参数之前。
函数不能修改它的任何参数。
它可以是函数指针，也可以是函数对象。
☉ 返回值
none.
☣ 示例
// 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
initial max heap : 30
max heap after pop : 20
max heap after push: 99
final sorted range : 5 10 15 20 99
✥ 复杂度
first and last的距离是线性的: 最多执行N*log(N)(其中N是距离)的元素比较， 最多执行一定数量的元素交换(或移动)。
⇄ 数据竞争
范围 [first,last)内的对象被修改。
☂ 异常安全性
如果任何元素比较，元素swap(或move)或迭代器操作抛出，则抛出。
注意，无效的参数会导致未定义的行为。
🍄 另请参阅
| pop_heap | 从堆范围中弹出元素(函数模板) |
| push_heap | 将元素插入堆范围(函数模板) |
| make_heap | 从范围构建堆(函数模板) |
| reverse | 反转元素(函数模板) |