std::make_heap() 算法

自 C++20 起

// (1)
template< class RandomIt >
constexpr void make_heap( RandomIt first, RandomIt last );

// (2)
template< class RandomIt, class Compare >
constexpr void make_heap( RandomIt first, RandomIt last, Compare comp );

直到 C++20

// (1)
template< class RandomIt >
void make_heap( RandomIt first, RandomIt last );

// (2)
template< class RandomIt, class Compare >
void make_heap( RandomIt first, RandomIt last, Compare comp );

检查范围 [first; last) 中的元素是否为最大堆。

• (1) 元素使用 operator< 进行比较。

• (2) 元素使用给定的二元比较函数 comp 进行比较。

参数

first last	用于创建堆的元素范围。
策略	要使用的执行策略。有关详细信息，请参阅执行策略。
比较	比较函数对象（即满足 Compare 要求的对象）。比较函数的签名应等同于以下内容： bool cmp(const Type1 &a, const Type2 &b); 签名不需要有 `const&`，但不得修改参数。 必须接受类型（可能是 const）Type 和 Type2 的所有值，无论值类别如何（因此不允许 Type1&，除非对于 Type1 移动等同于复制，否则也不允许 Type1 (C++11 起)） `Type1` 和 `Type2` 类型必须是 `RandomIt` 类型的对象可以隐式转换为它们两者的类型。

类型要求

RandomIt	LegacyRandomAccessIterator
解引用 RandomIt 的类型	MoveAssignable MoveConstructible

返回值

(无)

复杂度

最多 3 * std::distance(first, last) 次比较。

异常

带有模板参数 ExecutionPolicy 的重载报告错误如下

• 如果作为算法一部分调用的函数执行抛出异常，并且 ExecutionPolicy 是标准策略之一，则调用std::terminate。对于任何其他 ExecutionPolicy，行为是实现定义的.
• 如果算法未能分配内存，则抛出 std::bad_alloc。

备注

最大堆是具有以下属性的元素范围 [f; l)

• 给定 N 为 l - f，对于所有 0 < i < N，f[(i - 1) / 2] 不与 f[i] 比较小。
• 可以使用 std::push_heap 在 O(log(N)) 时间内添加新元素。
• 可以使用 std::pop_heap 在 O(log(N)) 时间内移除第一个元素。

示例

Main.cpp

#include <algorithm>
#include <functional>
#include <iostream>
#include <string_view>
#include <vector>

void print(std::string_view text, std::vector<int> const& v = {})
{
    std::cout << text << ": ";
    for (const auto& e : v) std::cout << e << ' ';
    std::cout << '\n';
}

int main()
{
    print("Max heap");

    std::vector<int> v {3, 2, 4, 1, 5, 9};
    print("initially, v", v);

    std::make_heap(v.begin(), v.end());
    print("after make_heap, v", v);

    std::pop_heap(v.begin(), v.end());
    print("after pop_heap, v", v);

    auto top = v.back();
    v.pop_back();
    print("former top element", {top});
    print("after removing the former top element, v", v);

    print("\nMin heap");

    std::vector<int> v1 {3, 2, 4, 1, 5, 9};
    print("initially, v1", v1);

    std::make_heap(v1.begin(), v1.end(), std::greater<>{});
    print("after make_heap, v1", v1);

    std::pop_heap(v1.begin(), v1.end(), std::greater<>{});
    print("after pop_heap, v1", v1);

    auto top1 = v1.back();
    v1.pop_back();
    print("former top element", {top1});
    print("after removing the former top element, v1", v1);
}

输出

Max heap:
initially, v: 3 2 4 1 5 9
after make_heap, v: 9 5 4 1 2 3
after pop_heap, v: 5 3 4 1 2 9
former top element: 9
after removing the former top element, v: 5 3 4 1 2

Min heap:
initially, v1: 3 2 4 1 5 9
after make_heap, v1: 1 2 4 3 5 9
after pop_heap, v1: 2 3 4 9 5 1
former top element: 1
after removing the former top element, v1: 2 3 4 9 5