社区讨论
求助!堆模板一直调不出来
学术版参与者 2已保存回复 2
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 2 条
- 当前快照
- 1 份
- 快照标识符
- @lou1fplx
- 此快照首次捕获于
- 2023/11/11 20:43 2 年前
- 此快照最后确认于
- 2023/11/11 22:00 2 年前
rt,这里是代码:
CPP#include <iostream>
#include <cstring>
using namespace std;
const int Csize=100005;
inline int ls(int x) {
return x*2;
}
inline int rs(int x) {
return x*2+1;
}
inline int fa(int x) {
return x/2;
}
template <typename T>
struct Heap { // 大顶堆
T val[Csize];
int cur;
Heap() {
memset(val,T(),sizeof(val));
}
void pushUp(T x) {
if(x==1) return ;
if(val[x]>val[fa(x)]) {
swap(val[x],val[fa(x)]);
pushUp(fa(x));
}
}
void pushDown(T x) {
if(x*2>cur) return ;
int son=ls(x);
if(rs(x)<=cur&&val[rs(x)]>val[son]) son=rs(x);
if(val[son]>val[x]) {
swap(val[son],val[x]);
pushDown(son);
}
}
void build(int a) {
cur=a;
for(int i=cur/2;i>=1;i--) {
pushDown(i);
}
}
void Delete() {
swap(val[1],val[cur--]);
pushDown(1);
}
void Insert(T x) {
val[++cur]=x;
pushUp(x);
}
T Top() {
return val[1];
}
};
int main() {
Heap<int> h;
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++) {
int a;
scanf("%d",&a);
h.Insert(a);
}
for(int i=1;i<=n;i++) {
printf("%d ",h.Top());
h.Delete();
}
return 0;
}
回复
共 2 条回复,欢迎继续交流。
正在加载回复...