堆

堆的定义

n个元素的序列{k1,k2,···,kn}当且仅当满足以下关系时，称之为堆：

$$\begin{cases} k_i \le k_{2i}\\ k_i \le k_{2i+1}\\ \end{cases} \quad或\quad\ \ \begin{cases} k_i \ge k_{2i}\\ k_i \ge k_{2i+1}\\ \end{cases}$$

前者称为小根堆，后者称为大根堆。
接下来，我们以小根堆为例对堆进行总结。
根据堆的定义，我们可以将堆表示成完全二叉树，给出一个小根堆的例子如下：

父节点一定小于等于两个孩子节点。

堆的存储

虽然用完全二叉树表示堆非常直观，但实际编程时通常采用数组模拟堆，依据下标处理相关联的元素。

const int N = 1e5 + 10;
int h[N];       //堆
int mySize;     //最末端的元素的下标

也经常使用C++的priority_queue来模拟堆。

堆的基础操作

实现一个堆的核心：

• down，节点的下沉操作
• up，节点上升操作

down

对一个节点，如果它大于某个孩子节点，就应该将该节点下沉，即与它最小的孩子节点交换位置，以满足堆的定义。

void down(int u)    //u为节点的下标
{                   //递归的使一个节点到达应到的位置
	int t = u;
	if (2 * u <= mySize && h[t] > h[2 * u])
		t = 2 * u;
	if (2 * u + 1 <= mySize && h[t] > h[2 * u + 1])
		t = 2 * u + 1;
	if (t != u)
	{
		swap(h[u], h[t]);   //下一层递归的入口
		down(t);
	}
}

up

对一个节点，如果它小于它的父节点，则应将其上升，即与父节点的位置互换，以满足堆的定义。

void up(int u)      //此处未用递归，但可以用递归实现
{
	while (u / 2)
	{
		if (h[u] >= h[u / 2])
			break;

		swap(u, u / 2);
		u /= 2;
	}
}

堆的初始化

给定一个元素集合，如何才将它变成一个堆：
从下标为mySize/2的元素开始，到下标为1的元素结束，分别执行一次down操作。

cin >> n;
mySize=n;
for (int i = 1; i <= n; i++)
	cin >> h[i];
for (int i = n / 2; i >= 1; i--)
	down(i);

对初始化的解释：
我们初始化就使要将原始的数据集合变成符合堆定义的数据集合。
二叉树的叶子节点没有孩子节点，因此必然满足定义中的方程，我们从最后一个不是叶子节点的节点开始逐个向前进行down操作，就可以使整棵二叉树满足定义变成堆。

堆的功能操作

对堆的功能操作有以下几种：

• 插入一个数
• 求堆中的最小值
• 删除任意一个数
• 修改任意一个数

插入

将其插在堆的末端，之后执行up操作。

int x;
cin >> x;
h[++mySize] = x;
up(mySize);

求最小值

最小值就是堆顶元素，即h[1]。
注意堆中元素下标从1开始，方便处理。

删除

将待删除元素与堆末端元素互换，mySize减一，再对交换过去的末端元素进行一次down操作，一次up操作(也可以判断该元素与父节点和子节点的关系具体选择一个操作，而直接一次up一次down就不用额外判断了)。

int x;
cin >> x;
swap(h[x], h[mySize--]);
up(x);
down(x);

修改

对某一元素修改后，执行一次down操作和一次up操作。

int k,x;
cin >> k >> x;
h[k] = x;
up(k);
down(k);

总结

对堆操作时，要时刻注意使堆中的元素满足堆定义中的方程，适时使用down和up操作。