标签：priority nums -- 创建元素 C++ 语法结构 queue heap

1.堆介绍

「堆 heap」是一种满足特定条件的完全二叉树，主要可分为图 8-1 所示的两种类型。

「大顶堆 max heap」：任意节点的值
其子节点的值。
「小顶堆 min heap」：任意节点的值
其子节点的值。

堆作为完全二叉树的一个特例，具有以下特性。

最底层节点靠左填充，其他层的节点都被填满。
我们将二叉树的根节点称为“堆顶”，将底层最靠右的节点称为“堆底”。
对于大顶堆（小顶堆），堆顶元素（即根节点）的值分别是最大（最小）的。

2.使用优先级队列（priority_queue）创建和维护堆

2.1 概念

堆（heaps）是一种特殊的数据组织方式，STL 中的 priority_queue 容器适配器底层就是采用堆来组织数据存储的。
实际上，堆通常用作实现优先队列，大顶堆相当于元素按从大到小顺序出队的优先队列。从使用角度来看，我们可以将“优先队列”和“堆”看作等价的数据结构。因此，这里对两者不做特别区分，统一使用“堆“来命名。

2.2 实例

C++标准库中的 std::priority_queue 是一种用于创建和维护堆的容器适配器。它提供了一种方便的方式来实现堆数据结构，通常用于处理具有优先级的元素。以下是使用 std::priority_queue 来创建和维护堆的使用介绍：

包含头文件：
```
#include <queue>
```

创建优先队列：

std::priority_queue<int> maxHeap; // 创建一个最大堆，默认情况下是最大堆
std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap; // 创建一个最小堆
std::priority_queue <int,vector<int>,less<int> > maxHeap;//创建一个最大堆

你可以创建一个最大堆（默认情况），或者通过提供第二个参数为 std::vector 和第三个参数为 std::greater 来创建一个最小堆。

插入元素：

使用 push 方法将元素插入堆中，堆会自动维护其性质。
```
maxHeap.push(10);
minHeap.push(5);
```
访问堆顶元素：

使用 top 方法可以访问堆顶元素，即最大值（最大堆）或最小值（最小堆）。
```
int max = maxHeap.top();
int min = minHeap.top();
```
移除堆顶元素：

使用 pop 方法可以移除堆顶元素，堆会自动维护其性质。
```
maxHeap.pop(); // 移除最大堆顶元素
minHeap.pop(); // 移除最小堆顶元素
```

检查堆是否为空：

使用 empty 方法可以检查堆是否为空。

bool isMaxHeapEmpty = maxHeap.empty();
bool isMinHeapEmpty = minHeap.empty();

获取堆中元素的数量：

使用 size 方法可以获取堆中元素的数量。
```
int maxHeapSize = maxHeap.size();
int minHeapSize = minHeap.size();
```
自定义比较函数：

如果你需要自定义比较函数来定义元素之间的比较规则，可以在创建优先队列时提供自定义比较函数。
```
struct Compare {
    bool operator()(int a, int b) {
        // 自定义比较规则
        return a > b; // 创建最小堆
    }
};

std::priority_queue<int, std::vector<int>, Compare> customHeap;
```
在上述例子中，我们创建了一个自定义的比较函数 Compare，它定义了创建一个最小堆。

std::priority_queue 简化了堆的创建和维护，特别适用于需要按优先级访问元素的问题，如任务调度、Dijkstra算法等。你可以根据问题的要求选择最大堆或最小堆，并通过提供自定义比较函数来实现更复杂的比较规则。

3.使用make_heap等系列函数创建和维护堆

3.1 概念

在C++中，make_heap、push_heap、pop_heap 和 sort_heap 是用于操作堆的四个标准库算法。这些算法用于处理堆数据结构，它们可以帮助你创建、维护和排序堆。以下是它们的用途和用法：

3.2 具体函数

make_heap：
- 用途：make_heap 用于将一个范围内的元素转化为一个堆（通常是最大堆或最小堆）。
- 语法：make_heap(first, last)，其中 first 和 last 分别是范围的起始迭代器和结束迭代器。
- 示例：
```
vector<int> nums = {3, 1, 4, 1, 5, 9, 2};
make_heap(nums.begin(), nums.end());
// nums 现在是一个最大堆，最大值 9 在根节点
```
push_heap：
- 用途：push_heap 用于将新元素添加到堆中，同时维护堆的性质。
- 语法：push_heap(first, last)，其中 first 和 last 定义了一个范围，范围内的元素是一个堆，且在 first 到 last - 1 之间添加了一个新元素。
- 示例：
```
vector<int> nums = {3, 1, 4, 1, 5};
nums.push_back(9);
push_heap(nums.begin(), nums.end());
// nums 现在是一个最大堆，最大值 9 在根节点
```
pop_heap：
- 用途：pop_heap 用于将堆的根节点（通常是最大值或最小值）取出，并将其放在范围的末尾，然后维护剩余元素的堆性质。
- 语法：pop_heap(first, last)，其中 first 和 last 定义了一个范围，范围内的元素是一个堆。
- 示例：
```
vector<int> nums = {9, 1, 4, 1, 5};
pop_heap(nums.begin(), nums.end());
// nums 现在是一个最大堆，最大值 9 被移至范围末尾
```
sort_heap：
- 用途：sort_heap 用于对一个堆进行排序，将堆中的所有元素按升序排列。
- 语法：sort_heap(first, last)，其中 first 和 last 定义了一个范围，范围内的元素是一个堆。
- 示例：
```
vector<int> nums = {9, 5, 4, 1, 1};
sort_heap(nums.begin(), nums.end());
// nums 现在是按升序排列的序列
```

这些堆算法对于处理堆数据结构非常有用，可以在各种算法和数据结构中使用。堆通常用于实现优先队列和解决一些最大值或最小值相关的问题。这些算法可以提高代码的可读性和效率，因为它们是经过精心设计和优化的标准库函数。

4.二者的区别和各自的优势

4.1 优先级队列优势

priority_queue 可以提供堆没有的优势，它可以自动保持元素的顺序；但我们不能打乱 priority_queue的有序状态，因为除了第一个元素，我们无法直接访问它的其他元素。如果需要的是一个优先级队列，这一点非常有用。

4.2 使用 make_heap()优势

从另一方面来说，使用 make_heap() 创建的堆可以提供一些 priority_queue 没有的优势：
1、可以访问堆中的任意元素，而不限于最大的元素，因为元素被存储在一个容器中，就像是我们自己的 vector。这也提供了偶然破坏元素顺序的可能，但是总可以调用 make_heap()来还原堆。
2、可以在任何提供随机访问迭代器的序列容器中创建堆。这些序列容器包括普通数组、string 对象、自定义容器。这意味着无论什么时候需要，都可以用这些序列容器的元素创建堆，必要时，可以反复创建。甚至还可以为元素的子集创建堆。

标签：priority,nums,--,创建,元素,C++,语法结构,queue,heap
From： https://www.cnblogs.com/trmbh12/p/17793906.html

C++ 语法结构--堆