C++中的堆
一、堆的概念
堆是一种特殊的树形数据结构，其每个节点都有一个值。通常所说的堆的数据结构，是指二叉堆，即完全二叉树。在C++中，标准库提供了一些用于操作堆的函数，如make_heap(), push_heap(), pop_heap()等。
二、堆的特点
- 每个节点的值都大于或等于（最大堆）或小于或等于（最小堆）其子节点的值；
- 堆是完全二叉树；
- 在堆中，父节点的值总是大于或等于（最大堆）或小于或等于（最小堆）其子节点的值；
- 堆的根节点是整个堆的最大值（或最小值）。
三、堆的实现原理
- 建立堆：首先将元素插入到数组中，然后通过调整数组中的元素，使其满足堆的性质。这个过程通常使用
make_heap()函数来完成。 - 调整堆：在插入新元素后，需要调整堆以保持其性质。这个过程通常使用
push_heap()函数来完成。 - 删除堆顶元素：在需要删除堆顶元素时，首先需要将堆调整为最大堆或最小堆，然后再进行删除操作。这个过程通常使用
pop_heap()函数来完成。
四、堆的算法流程
- 插入元素：首先将元素插入到数组中，然后通过调整数组中的元素，使其满足堆的性质。
- 调整堆：在插入新元素后，需要调整堆以保持其性质。这个过程通常使用
push_heap()函数来完成。 - 删除堆顶元素：在需要删除堆顶元素时，首先需要将堆调整为最大堆或最小堆，然后再进行删除操作。这个过程通常使用
pop_heap()函数来完成。 - 获取最大/小值：如果需要获取当前堆的最大值或最小值，可以使用
top()函数来获取。如果需要获取最大/小值的索引，可以使用bottom()函数来获取。
五、C++代码示例
#include<bits/stdc++.h> // 引入头文件，包含了常用的标准库函数和数据结构
#define reg register // 定义宏，表示使用寄存器变量
using namespace std; // 使用命名空间std，简化代码书写
// 定义一个函数read()，用于读取输入的整数，支持负数输入
inline int read(){
int x=0,f=1; // 初始化变量x为0，f为1
char ch=getchar(); // 读取一个字符作为输入
while(ch<'0'||ch>'9'){ // 如果输入不是数字，则继续读取
if(ch=='-') f=-1; // 如果输入是负号，则将f设为-1
ch=getchar(); // 读取下一个字符
}
while(ch>='0'&&ch<='9'){ // 如果输入是数字，则转换为整数并计算结果
x=(x<<1)+(x<<3)+(ch^48); // 将x左移1位并加上x左移3位再加上ch与48的异或值
ch=getchar(); // 读取下一个字符
}
return x*f; // 返回计算结果，如果f为-1，则返回负数结果
}
// 定义一个函数write()，用于输出整数，支持负数输出
void write(int x){
if(x<0){ // 如果x是负数，则先输出负号
putchar('-');
x=-x; // 取绝对值
}
if(x>9) write(x/10); // 如果x大于9，则递归调用write()函数输出除以10的结果
putchar(x%10+'0'); // 输出x除以10的余数，并转换为字符输出
return ;
}
int n; // 声明一个整数变量n，用于存储操作的次数
priority_queue<int, vector<int > ,greater<int > > a; // 声明一个优先队列a，用于存储整数，默认为大顶堆
int main(){
n=read(); // 读取操作次数n
while(n--){ // 循环执行n次操作
int op=read(); // 读取操作类型op
if(op==1){ // 如果操作类型op为1，则读取一个整数x，并将其插入到优先队列a中
int x;
scanf("%d",&x);
a.push(x);
continue;
}
if(op==2){ // 如果操作类型op为2，则输出优先队列a的顶部元素（即最小值）
printf("%d\n",a.top());
continue;
}
if(op==3){ // 如果操作类型op为3，则弹出优先队列a的顶部元素（即最小值）
a.pop();
}
}
return 0; // 程序执行完毕，返回0
}
在这个例子中，我们首先定义了一个大小为100的数组作为堆，然后插入了三个元素3、5和1。最后，我们调用pop_max()函数来删除并返回堆中的最大元素。