目录
向上调整算法（默认小堆）
向下调整算法（默认小堆）
利用向上调整算法对现有数组直接建堆
利用向下调整算法对以建成的小堆数组排降序
举一反三： 那么如何将数组 a 排成升序呢？
向上调整算法（默认小堆）
// 数据类型
typedef int HPDataType;
// 交换
void Swap(HPDataType* p1, HPDataType* p2)
{
HPDataType tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
// 向上调整
void AdjustUp(HPDataType* a, int child)
{
int parent = (child - 1) / 2;
while (child > 0)
{
if (a[child] < a[parent])
{
// 交换
Swap(&a[child], &a[parent]);
// 迭代
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}不改变堆的结构，那么就要堆当前插入的数据向上调整
而且当前插入的数据只会影响其父亲节点，或者父亲的父亲节点，直到根节点
把当前插入的数据的下标比作 child，那么就可以通过 (child-1)/2 这个公式找到其父亲节点
再通过比较判断是否需要向上交换并且迭代
当不满足 if 条件时，说明当前插入的数据还是堆结构，直接跳出循环即可
向下调整算法（默认小堆）
static void AdjustDown(HPDataType* a, int size, int parent)
{
int child = parent * 2 + 1;
while (child < size)
{
// 先找到左右孩子中小的那个
if ((child + 1 < size) && (a[child + 1] < a[child]))
child++;
if (a[parent] > a[child])
{
// 交换
Swap(&a[parent], &a[child]);
// 迭代
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}向下调整算法是在把堆顶元素删除后进行的
向下调整算法的前提：根节点的左右子树已经是一个堆，才能向下调整
删除堆顶元素，要保持堆大致不变，所以把首尾元素交换，交换后删除堆顶元素也就是删除尾元素
删除后，尾元素就到了堆顶，但是要确保堆结构不变，所有要对尾元素向下调整
根据 parent*2+1 的公式，找到根节点的右孩子，左右孩子存在的情况下比较
当尾元素大于小的那个孩子就需要交换，再迭代，直到不满足 if 条件，就跳出循环
此时就完成了向下调整算法
利用向上调整算法对现有数组直接建堆
现有一个整型数组：
int a[] = { 5,7,3,9,1,8,4,6,2 };
对数组直接建堆的方法：
把数组中的第一个元素当作堆，因为堆的本质就是完全二叉树，那么只有一个元素的时候，也可以看着一颗完全二叉树，只是这颗完全二叉树只有根节点
再从数组中的第二个元素开始遍历，利用向上调整算法模拟堆的插入过程
遍历完后，数组 a 就变成了一个小/大堆
代码演示：
void HeapSort(int* a, int size)
{
// 从第二个元素开始遍历
for (int i = 1; i < size; i++)
{
// 向上调整
AdjustUp(a, i);
}
}代码验证：
1
/ \
2 4
/ \ / \
3 7 8 5/ \
9 6
利用向下调整算法对以建成的小堆数组排降序
代码演示：
void HeapSort(int* a, int size)
{
// 从第二个元素开始遍历
for (int i = 1; i < size; i++)
{
// 向上调整（建小堆）
AdjustUp(a, i);
}
// a 数组调整为降序
for (int i = size - 1; i >= 0; i--)
{
// 首尾交换
Swap(&a[0], &a[i]);
// 向下调整
AdjustDown(a, i, 0);
}
}代码解析：
第一个 for 循环完成了对数组 a 进行建堆，上方已有讲解
建堆之后，数组 a 此时就是一个小堆的结构
小堆结构的特点就是堆顶元素是整个堆元素中最小的元素
那我们就可以将首尾元素交换，也就是数组 a 的第一个元素和最后一个元素交换
交换后，最小的元素就排到了最后的位置，然后就不用再动最后一个元素了
把前 size-1 个元素看作新的堆，利用向下调整算法，把前 size-1 个元素建堆，同样是建小堆
建好后，那么第二小的数据就到了数组首元素的位置，再次首尾交换，重复以上动作
最后就能将数组 a 排成降序
代码验证：
举一反三： 那么如何将数组 a 排成升序呢？
第一步：
同样是利用向上调整算法对已有的数组进行建堆，但是不同的是需要建立大堆
只需要将向上调整算法中的小于符号变为大于符号
第二步：
对数组 a 建成大堆后，再利用首尾交换和向下调整算法对数组 a 进行排升序
因为数组 a 的是大堆，大堆的特点就是堆顶元素是数组所有元素中最大的数
所以首尾交换后，最大的数就在最后的位置，再把前 size-1 的元素看作新的大堆
利用向下调整算法把第二大的元素调整到堆顶，再首尾交换，把第二大的元素放在倒数第二的位置
循环结束后，数组 a 就调整成了升序数组
需要注意的是：向下调整算法也需要更改符号，要更改的是两点，一是左右孩子中，找大的，二是当堆顶元素小于左右孩子中的大那个时就交换
代码验证：