一、引言
在堆中，我们常常需要用到两个算法：向上调整算法和向下调整算法。
对于堆的“增” “删”而言，需要将堆保持原来的大小堆序，需要对数据修调整后，对堆进行调整。
此时 增，需要用到向上调整算法； 删， 需要用到向下调整算法。
二、算法介绍
1.向上调整算法:
条件：
保证其余数据满足堆
顺着宗族线往上走
已知孩子，找父亲。
公式：
leftchild = parent * 2 +1
rightchild = parent * 2 +2
parent = (child - 1) / 2
实现：
//前提：再调整之前，已经是一个大、小堆
void AdjustUp(HPDataType* a, int child) //通过 调整 向上算法，可以实现 大小堆 的转换。
{
int parent = (child - 1) / 2;
//while (parent >= 0)
while(child > 0)
{
if (a[child] > a[parent])
{
Swap(&a[child], &a[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
需要注意的是，需要通过child = parent； parent = （child - 1 ） / 2；这两个语句，保证数组遍历不断往下进行。
2.向下调整算法：
前提：
在调整之前，左、右子树（除根的部分）是大、小堆。
执行：
建立大堆：找大孩子；建立小堆，找小孩子。
代码：
void AdjustDown(int* a, int n, int parent) //下调从parent开始。上调从child开始
{
int child = parent * 2 + 1; //默认左孩子小。 左孩子存在，不一定有右孩子，左孩子不存在，一定没有右孩子
while (child < n) //孩子不存在（n是大小，不是下标）
{
// 选出左右孩子中小/大的那个
if (child + 1 < n //child + 1 < n 如果 有孩子存在（下标符合规范） 判断语句必须写在之前！否则默认child + 1 合法（[ ] 会检查越界）
&& a[child+1] > a[child]) //child + 1 是右孩子的下标
{
++child;
}
if (a[child] > a[parent])
{
Swap(&a[parent], &a[child]);
parent = child;
child = parent * 2 + 1; //默认左孩子
}
else
{
break;
}
}
}
需要注意的是，使用下标，必须要进行下标范围的检查，防止越界。
三、算法复杂度
时间复杂度为O（logN）
原因：最多需要遍历的次数为树的高度。
