本篇总结堆排序是如何实现的，以及各种细节问题，两种不同的建堆方法以及各自的使用场景，注意排序利用堆删除思想进行处理
⏰堆排序
🕚建堆
建什么样的堆根据需求来决定
如果要排升序则建大堆
如果要排降序则建小堆
而建堆的方法有两种方法可以使用，一种是利用向上调整法建堆，即模拟插入建堆，一种是向下调整法建堆。不过通常堆排序中使用的建堆方法是向下调整建堆，因为向下调整建堆的方法效率要高。
并且在排序中也是使用向下调整思想进行排序，所以我们如果掌握了向下调整的思想，也就可以学会堆排序了。
向上调整建堆通常使用在堆中一开始没有数据，后来数据才进堆中，需要不断的往堆中插入，这样使用向上调整建堆很方便。因为数据只有在堆上面，下面也没有数据，使用向下调整很困难，而且低效。
而向下调整建堆长使用在已有数据，对已有数据进行建堆，也就是给你一个数组，让你进行排序就是很适合利用向下调整法进行建堆。
◽向上调整建堆
如何使用向上调整法建堆呢？
首先我们要理解向上调整的思想，即堆最后一个元素，顺着双亲往上调整即可
【建大堆】如果要建大堆则要求父结点元素大于子结点元素，如果不满足则两个结点值交换。
【建小堆】如果要建小堆则要求父节点元素小于子结点元素，如果不满足则两个结点值交换。
所以如果给定一个数组，我们如何使用向上调整法对这个数组建堆呢？
我们可以默认让数组第一个元素为堆顶元素，从数组第二个元素开始进行向上调整，调整完再调整数组第三个元素，……就这样调整n-1个元素就可以了。
void AdjustUp(int* a, int child)//向上调整的前提就是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; } } }
建堆：
//向上调整建堆--模拟插入建堆，时间复杂度为N*logN for (int i = 1; i <10; i++)//从第二个元素开始调整，默认第一个元素为堆顶元素 { AdjustUp(a, i);//i就是每次要调整的元素下标 }
◽向下调整建堆
如何使用向下调整法进行建堆呢？
首先还是要理解向下调整法的思想
从堆顶元素开始往下调整，如果不满足要调整的堆性质，就要交换。
在已有数据的基础上我们进行建堆
下面我们给出一个数组，这个数组逻辑上可以看做一颗完全二叉树，但是还不是一个堆，现在我们通过算法，把它构建成一个堆。根节点左右子树不是堆，我们怎么调整呢？这里我们从倒数的第一个非叶子节点的子树开始调整，一直调整到根节点的树，就可以调整成堆。
int a[] = {1,5,3,8,7,6};
倒数第一个非叶子，或者最后一个叶子的父亲。
为什么这样调？
我们知道，向下调整有前提条件，要求左右子树都为大堆或小堆。
我们从后面开始调，从最后一个叶子的父亲开始调，调完父亲，再调父亲的兄弟，那父亲和兄弟都调整完，父亲的父亲就可以调整了，因为父亲和兄弟那串子树都为堆了已经。 只要左右子树为堆我们就可以用向下调整。
要从最后一个子叶的父节点开始调整，首先我们需要找到它
对于数组来说，最后一个子叶的父亲的位置在哪呢？
最后一个结点的位置是n-1，而它的父节点的位置是((n-1)-1)/2 ,即(n-2)/2.
从这个位置开始向下调整，直到堆顶元素调整完即可
void AdjustDown(int* a, int n, int parent)//实现的前提是左右子树都是堆 { int child = parent * 2 + 1; while (child < n) { //选出左右孩子中比较大的孩子，假设child为左边，假设左边孩子比较大 if (child + 1 < n && a[child] < a[child + 1])//不过这里存在越界的风险，不能保证右边的孩子一定存在 {//右边的孩子要存在的话也需要小于n才可以所以我们再加上去 ++child;//让右边的孩子成为比较大的child } //然后让根（父亲）与较大儿子比较，这里是大堆，父亲要大于儿子的 if (a[parent] >a[child]) { Swap(&a[parent], &a[child]); //交互完后，让parent跳到儿子位置上去，儿子继续往下找 parent = child; child = parent * 2 + 1; } else { break; } } }
建堆：
//通常建堆是使用向下调整建堆--怎么使用向下调整建堆呢？ //从最后一个非空子叶开始向下调整，调整完后，再调整它的兄弟，再调整它们的父辈 for (int i = (n -2) / 2; i >= 0; i--) { AdjustDown(a, n, i); }
◽两者区别：时间复杂度不同
向上调整的时间复杂度是O(N*logN)
而向下调整的时间复杂度是O(N)
也正是它们效率的不同，通常建堆常使用向下调整建堆，效率高。
🕐排序
利用堆删除思想进行排序
建完堆后，就要对堆中数据进行排序了。
那怎么排序呢？
比如我们排升序，我们要求的是第一个元素应该是最小的才对。
最后一个元素才是最大的。但我们建的是大堆，而大堆的堆顶数据是最大的，也就是数组第一个元素最大，完全不符合排序嘛。
我们是这样做：将堆顶数据与最后一个数据交换，并不删除最后一个元素，只是将堆的范围缩小，从堆顶开始往下调整使它的性质恢复。
然后再接着将堆顶与倒数第二个交换，交换完后，堆的范围缩小，从堆顶向下调整。
//将堆顶数据与堆尾部数据交换，然后不要删除最后这个数据，让剩下的n-1个结点继续变成堆，然后继续交换 int end = n - 1;//堆尾数据 for (int i = 0; i < n; i++) { Swap(&a[0], &a[end]); AdjustDown(a, end, 0);//end就是每次要调整堆的大小，每次都会缩小1 end--; }
⏰整体代码
void HeapSort(int* a, int n)//堆排序 { //建堆 for (int i = (n - 1 - 1) / 2; i >= 0; i--) { AdjustDown(a, n, i); } //排序 int end = n - 1; for (int i = 0; i < n; i++) { Swap(&a[0], &a[end]); AdjustDown(a, end, 0); end--; } } int main() { int a[20] = { 9,5,2,3,6,7,8,4,1,0 }; HeapSort(a, 10); return 0; }
