社区讨论

求助!堆模板一直调不出来

学术版参与者 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 条回复,欢迎继续交流。

正在加载回复...