[数据结构与算法]数据结构（堆）

#include<iostream>

using namespace std;

const int N = 1e6 + 10;

int h[N], Size;//size 堆的大小
int n;

void down(int u) 
{
	int t = u;
	if (u * 2 <= Size && h[u * 2] < h[t])t = u * 2;
	if (u * 2 + 1 <= Size && h[u * 2 + 1] < h[t])t = u * 2 + 1;
	if (u != t) 
	{
		swap(h[u], h[t]);
		down(t);
	}
}

void up(int u)
{
	if (u <= 1)return;
	if (h[u] < h[u / 2])
	{
		swap(h[u], h[u / 2]);
		up(u / 2);
	}
}

int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)cin >> h[i];

	for (int i = n / 2; i; i--)down(i);//从n/2开始时间复杂度更低

	return 0;
}