个人用笔记
2025-08-10 20:33:32
发布于：浙江
37阅读
0回复
0点赞
堆模版
#include<iostream>
using namespace std;
const int MAXN = 1e6+7; // 结点的数量
int a[MAXN]; // 保存每个结点的权值 小根堆
int last ; // 记录树的结点总数
void Insert(int x){ // 传入要插入的数字
a[++last] = x ; // 插入最后一个结点
int it = last ; // 获取当前结点编号
while(it > 1){
int fa = it / 2; // 获取父亲结点
// 父亲结点小于等于孩子结点 已经合法了 退出
if(a[fa] <= a[it]) break ;
swap(a[fa],a[it]); // 不合法 交换
it = fa; // 更新当前结点
}
}
void Delete(){
// 删除根结点
cout << a[1] << " " ;
a[1] = a[last -- ]; // 覆盖根结点
int it = 1;
while(it * 2 <= last){
// 有孩子结点可以比较
int son = it * 2 ;
if(son + 1 <= last && a[son + 1] < a[son]) son ++ ; // 右孩子更优
if(a[it] <= a[son])break ; // 已经合法 不需要更新
swap(a[it],a[son]);
it = son ; // 迭代下标向下比较
}
}
int main(){
int n;
cin >> n;
for(int i = 1 ; i <= n ; i ++ ){
int x;
cin >> x;
Insert(x);
}
// for(int i = 1 ; i <= last ; i ++ ){
// cout << a[i] << " ";
// }
while(last){
Delete();
}
return 0;
}
有帮助，赞一个