关于手写堆
  • 板块学术版
  • 楼主tder
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/12/16 13:37
  • 上次更新2023/12/16 13:38:33
查看原帖
关于手写堆
714254
tder楼主2023/12/16 13:37

已知 pop() 有一定问题,求调。

struct heap {
	int a[N], t = 0;
	int size() {
		return t;
	}
	int empty() {
		return !size();
	}
	int push(int k) {
		a[++t] = k;
		int c = t;
		while(a[c] > a[c / 2] && c > 1) {
			swap(a[c], a[c / 2]);
			c /= 2;
		}
		return c;
	}
	int top() {
		assert(size());
		return a[1];
	}
	void pop() {
		assert(size());
		swap(a[1], a[t--]);
		int c = 1;
		while(a[c] < max(a[c * 2], a[c * 2 + 1]) && c * 2 <= t) {
			if(a[c * 2] > a[c * 2] + 1 || c * 2 == t) {
				swap(a[c], a[c * 2]);
				c *= 2;
			} else {
				swap(a[c], a[c * 2 + 1]);
				c *= 2, c += 1;
			}
		}
	}
};
2023/12/16 13:37
加载中...