Namespaces
Variants

    std::sort_heap

    来自 zh.cppreference.net
     
    C++
     
    算法库
    受约束算法和范围上的算法 (C++20)
    受约束算法，例如 ranges::copy, ranges::sort, ...
    排序及相关操作
    划分操作
    (C++11)    
    (C++11)

    排序操作
    二分查找操作
    (在划分后的范围上)
    集合操作（在已排序范围上）
    合并操作（在已排序范围上）
    堆操作
    最小/最大操作
    (C++11)
    (C++17)
    字典序比较操作
    (C++20)
    排列操作


     
    定义于头文件 <algorithm> 
    template< class RandomIt >
void sort_heap( RandomIt first, RandomIt last );
    		(1) (自C++20起为constexpr) 
    template< class RandomIt, class Compare >
void sort_heap( RandomIt first, RandomIt last, Compare comp );
    		(2) (自C++20起为constexpr)

    将堆 [first, last)转换为有序范围。堆属性不再保持。

    1) 堆相对于 operator<(直至 C++20)std::less{}(自 C++20 起)，并将相对于 operator<(直至 C++20)std::less{}(自 C++20 起)进行排序。
    2) 堆相对于 comp，并将相对于 comp进行排序。

    如果满足以下任一条件，则行为未定义：

    • [first, last)不是一个堆。
    (直至 C++11)
    (自 C++11 起)

    参数

    first, last - 定义待排序 范围 的二叉堆元素迭代器对
    comp - 比较函数对象（即满足 Compare 要求的对象），当第一个参数 小于 第二个参数时返回 true 。

    比较函数的签名应等价于如下形式：

    bool cmp ( const Type1 & a, const Type2 & b ) ;

    虽然签名不需要包含 const & ，但函数不得修改传递的对象，且必须能够接受所有 Type1 与 Type2 类型的值（包括const类型），无论其 值类别 为何（因此不允许使用 Type1 & ，也不允许使用 Type1 ，除非对于 Type1 类型移动操作与拷贝操作等效 (C++11 起) ）。
    类型 Type1 与 Type2 必须使得 RandomIt 类型的对象在解引用后能隐式转换到这两个类型。

    类型要求
    -
    RandomIt 必须满足 LegacyRandomAccessIterator 的要求。
    -
    Compare 必须满足 Compare 的要求。

    复杂度

    给定 N 为 std:: distance ( first, last ) ：

    1) 最多进行 2N⋅log(N) 次比较，使用 operator < (C++20 前) std:: less { } (C++20 起) 。
    2) 最多 2N⋅log(N) 次比较函数 comp 的应用。

    可能的实现

    堆排序 (1) 
    template<class RandomIt>
void sort_heap(RandomIt first, RandomIt last)
{
    while (first != last)
        std::pop_heap(first, last--);
}
    堆排序 (2) 
    template<class RandomIt, class Compare>
void sort_heap(RandomIt first, RandomIt last, Compare comp)
{
    while (first != last)
        std::pop_heap(first, last--, comp);
}

    示例

    运行此代码 
    #include <algorithm>
#include <iostream>
#include <string_view>
#include <vector>
void println(std::string_view fmt, const auto& v)
{
    for (std::cout << fmt; const auto &i : v)
        std::cout << i << ' ';
    std::cout << '\n';
}
int main()
{
    std::vector<int> v{3, 1, 4, 1, 5, 9};
    std::make_heap(v.begin(), v.end());
    println("after make_heap, v: ", v);
    std::sort_heap(v.begin(), v.end());
    println("after sort_heap, v: ", v);
}

    输出： 

    after make_heap, v: 9 4 5 1 1 3
after sort_heap, v: 1 1 3 4 5 9

    缺陷报告

    以下行为变更缺陷报告被追溯应用于先前发布的C++标准。

    缺陷报告 适用范围 发布时行为 正确行为
    LWG 2444 C++98 最多允许 N⋅log(N) 次比较 提升至 2N⋅log(N) 次比较

    另见

    (C++11)
    		 检查给定范围是否为最大堆
    (函数模板 & 算法函数对象)
    (C++20)
    (C++11)
    		 找到作为最大堆的最大子范围
    (函数模板 & 算法函数对象)
    (C++20)
    		从元素范围创建一个最大堆
    (函数模板 & 算法函数对象)
    (C++20)
    		从最大堆中移除最大元素
    (函数模板 & 算法函数对象)
    (C++20)
    		向最大堆添加一个元素
    (函数模板 & 算法函数对象)
    (C++20)
    (C++20)
    		 将最大堆转换为元素的有序范围
    (算法函数对象)