void push_heap(_RanIt _First, _RanIt _Last)

void push_heap(_RanIt _First, _RanIt _Last) 是 C++ STL 中 <algorithm> 头文件提供的一个函数，用于维护一个堆的性质。特别地，它用于将一个元素加入到一个已排序（堆化）的区间（通常是一个堆容器），并重新调整堆的结构。

函数原型：

void push_heap(_RanIt _First, _RanIt _Last);

参数说明：

• _First：堆序列的起始迭代器。
• _Last：堆序列的结束迭代器。_Last 通常指向一个超出最后一个元素的迭代器（即一块区域的尾后位置）。

功能：

• 堆的性质：一个堆是一个完全二叉树，并且每个父节点的值满足堆的性质：

  • 最大堆：父节点的值总是大于或等于其子节点的值。
  • 最小堆：父节点的值总是小于或等于其子节点的值。

  默认情况下，push_heap 会操作一个最大堆。

• push_heap 会将 _Last-1 位置的元素插入到已经是堆结构的区间 [First, Last-1) 中，并保持堆的性质不变。它不会在区间中添加元素，而是通过调整已有元素的位置来确保堆的性质。

• 在 C++ 中，push_heap 和 pop_heap 是对一个区间进行堆操作的两个核心函数，通常配合使用。

使用过程：

1. 你首先有一个已经排序的堆，存储在一个容器中。
2. 然后你调用 push_heap 来插入一个新的元素。
3. push_heap 会调整这个新元素的位置，以保证堆的结构和性质依然保持。

工作原理：

假设你有一个容器 heap，其中已经存储了一些元素并且这些元素满足堆的性质。你使用 push_heap 将新的元素添加到容器的末尾，push_heap 会将这个新元素上浮到合适的位置，重新调整堆。

代码示例：

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    // 创建一个空的最大堆
    std::vector<int> heap = {20, 15, 10, 5, 8, 7};

    // 使用 make_heap 将一个数组/容器转为堆
    std::make_heap(heap.begin(), heap.end());

    // 显示当前堆内容
    std::cout << "Heap before push_heap: ";
    for (int x : heap) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    // 插入新元素 25
    heap.push_back(25);
    std::push_heap(heap.begin(), heap.end());  // 调整堆结构

    // 显示调整后的堆
    std::cout << "Heap after push_heap: ";
    for (int x : heap) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    return 0;
}

输出：

Heap before push_heap: 20 15 10 5 8 7 
Heap after push_heap: 25 20 10 15 8 7 5 

代码解析：

1. std::make_heap(heap.begin(), heap.end())：这个函数将 heap 向量中的元素构造为一个最大堆。
2. heap.push_back(25)：将新元素 25 添加到堆的末尾。
3. std::push_heap(heap.begin(), heap.end())：调整堆结构，保证堆的性质。因为新元素 25 被添加到了堆的末尾，它会被上浮到合适的位置。

特点：

• push_heap 操作的时间复杂度是 O(log N)，其中 N 是堆中元素的数量。
• 它只会调整堆，而不直接改变其他非堆元素的位置。

注意：

• push_heap 只会在容器的末尾添加元素，并确保堆的性质。它并不会在容器中间插入元素。
• 你可以使用 pop_heap 函数来移除堆顶元素，并通过堆化调整堆结构。

总结：

push_heap 是在一个已经是堆的容器中插入一个新元素并保持堆结构的一个非常有用的函数。它通过上浮新元素来保持堆的性质，是堆排序算法和优先队列的基础。

---

void sort_heap(_RanIt _First, _RanIt _Last)

在 C++ 中，sort_heap 是一个标准库函数，用于将一个已经是堆结构的数据范围（通过 push_heap 或 make_heap 创建的堆）重新排序为一个 升序排序 的范围。它的作用是把堆顶的元素放到最前面，并且保持堆的性质。

函数原型

template <class _RanIt>
void sort_heap(_RanIt _First, _RanIt _Last);

参数说明：

• _First：指向需要排序范围的起始迭代器。
• _Last：指向需要排序范围的末尾迭代器。

返回值：

sort_heap 没有返回值，它直接对所给范围 [first, last) 内的元素进行排序。

作用：

sort_heap 将一个已经是堆的数据结构（即满足堆的性质）转换为一个 升序排序 的序列。如果数据原本是一个最大堆（堆顶元素最大），它将被排序成升序的序列；如果数据原本是最小堆（堆顶元素最小），则将被排序成降序的序列。

使用场景：

sort_heap 通常用于当我们希望使用堆排序算法对数据进行排序时。你首先需要通过 make_heap 或 push_heap 构建一个堆，然后调用 sort_heap 来将堆排序成一个升序序列。

使用步骤：

1. 使用 make_heap 创建一个堆。
2. 使用 sort_heap 对堆进行排序。

代码示例

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    // 初始化一个数组
    std::vector<int> vec = {10, 20, 15, 30, 40};

    // 使用 make_heap 构建一个最大堆
    std::make_heap(vec.begin(), vec.end());

    std::cout << "Heap before sort_heap: ";
    for (int val : vec) {
        std::cout << val << " ";
    }
    std::cout << std::endl;

    // 使用 sort_heap 将堆排序成升序
    std::sort_heap(vec.begin(), vec.end());

    std::cout << "Heap after sort_heap: ";
    for (int val : vec) {
        std::cout << val << " ";
    }
    std::cout << std::endl;

    return 0;
}

输出：

Heap before sort_heap: 40 30 15 10 20 
Heap after sort_heap: 10 15 20 30 40 

解释：

1. 创建堆： 使用 std::make_heap 函数将数组 vec 转换成一个最大堆。最大堆的性质是每个节点的值都大于或等于其子节点的值。

2. 排序堆： 使用 std::sort_heap 对堆进行排序。sort_heap 会依次把堆顶的元素（即最大值）移动到序列的尾部，逐步构建出一个升序排列的序列。

注意事项：

• 必须保证调用 sort_heap 的范围本身已经是一个堆结构（通过 make_heap 或 push_heap 创建），否则 sort_heap 的行为未定义。
• sort_heap 并不适用于普通的无序数组。如果数组不是堆，调用 sort_heap 会导致错误的排序结果。
• sort_heap 的时间复杂度是 O(n log n)，和 std::sort 的时间复杂度相同。

总结：

sort_heap 是一种堆排序的方法，它只对已经满足堆条件的数据进行排序。通过使用 make_heap 或 push_heap 可以将数据组织成堆，进而用 sort_heap 来进行排序。这与 std::sort 不同，std::sort 适用于任何普通的无序数据，而 sort_heap 只适用于堆。