堆排序代码

int heap[100001], len, n;
inline void up(int k) {
	while (k > 1 && heap[k] < heap[k / 2]) {
		swap(heap[k], heap[k / 2]);
		k /= 2;
	}
}
inline void down(int k) {
	while (k + k <= len) {
		int j = k + k;
		if (j + 1 <= len && heap[j + 1] < heap[j])//下滤要选择儿子中的小的那个，这里我们当作每个都有两个儿子
			j++;
		if (heap[k] < heap[j])
			break;
		swap(heap[k], heap[j]);
		k = j;
	}
}
int main()
{
	cin >> n;
	len = 0;
	for (int i = 1; i <= n; i++) {
		int x;
		cin >> x;
		heap[++len] = x;
		up(len);//这里上滤或者下滤都一样滴
	}
	for (int i = 1; i <= n; i++) {
		cout << heap[1] << ' ';
		swap(heap[1], heap[len]);
		len--;//利用堆删掉一个之后剩下的位置来储存堆顶元素，这样的话，重新输出heap数组将会得到一个降序数组！！！
		down(1);
	}
	return 0;
}