数据结构 ——— 向上/向下调整算法将数组调整为升/降序

向上调整算法（默认小堆）

向下调整算法（默认小堆）

利用向上调整算法对现有数组直接建堆

利用向下调整算法对以建成的小堆数组排降序

举一反三：那么如何将数组 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 就调整成了升序数组
需要注意的是：向下调整算法也需要更改符号，要更改的是两点，一是左右孩子中，找大的，二是当堆顶元素小于左右孩子中的大那个时就交换

代码验证：