1、堆的应用 -- 堆排序
堆是一个完全二叉树，完全二叉树用数组存储数据最优。
堆排序即利用堆的思想来进行排序，总共分为两个步骤：
1、建堆
升序：建大堆
降序：建小堆
2、利用堆删除的思想来进行排序
建堆和堆删除中都用到了向下调整，因此掌握了向下调整，就可以完成堆排序。
1.1 堆排序的思路分析
我们本篇文章使用小堆进行讲解，小堆排序是降序。
对堆还不是很了解的同学可以浅看一下堆的那篇文章：戳这里即可跳转
1、我们先对数组里的元素进行向下调整建成小堆；
2、小堆的堆顶元素肯定是数组中最小的，因此我们将堆顶元素（数组首元素）与数组尾元素交换，将数组尾元素不在看作是数组中的元素（size--），再从堆顶开始向下调整重新构建小堆，不断重复就可以实现降序排序（升序只要将小堆改为大堆就可以实现）。
2、建堆
我们建堆可以使用向上调整建堆，也可以使用向下调整建堆，我们该如何选择呢？
那肯定是谁的时间复杂度小我就选谁，那接下来我们分析一下两种建堆的时间复杂度：
2.1 向上调整建堆：O(N*logN)
2.1.1 向上调整代码
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; } } }
2.1.2 向上调整建堆代码
//建堆 -- 向上调整，时间复杂度：O(N*log(N)) for (int i = 0; i < size; i++) { AdjustUp(a, i); }
我们画图来分析一下向上调整建堆时间复杂度：
堆是一个完全二叉树，满二叉树也是完全二叉树，因此我们以满二叉树为例推出向上调整建堆的时间复杂度为O(N*logN)。
2.2 向下调整建堆：O(N)
2.2.1 向下调整代码
void AdjustDown(HPDataType* a, int size, int parent) { int child = parent * 2 + 1; while (child < size)//当child大于了数组大小就跳出循环 { //找出左右孩子中小/大的那个（假设法） if (child + 1 < size && a[child + 1] < a[child]) { child++; } if (a[child] < a[parent]) { Swap(&a[parent], &a[child]); parent = child; child = parent * 2 + 1; } else { break; } } }
2.2.2 向下调整建堆代码
for (int i = (size - 1 - 1) / 2; i >= 0; i--) { AdjustDown(a, size, i); }
我们画图来分析一下向下调整建堆时间复杂度：
向下调整建堆时间复杂度：O(N)。
如此分析下来我们就可以知道，向下调正建堆才是最优选择。
3、堆排序实现代码
//堆排序时间复杂度O(N + N*logN) void HeapSort(int* a, int size) { //升序 -- 建大堆 //降序 -- 建小堆 //建堆 -- 向上调整，时间复杂度：O(N*log(N)) //for (int i = 0; i < size; i++) //{ // AdjustUp(a, i); //} //建堆 -- 向下调整，时间复杂度：O(N) //倒着调整 //叶子节点不需要处理 //倒数第一个非叶子节点：最后一个节点的父亲开始调整 for (int i = (size - 1 - 1) / 2; i >= 0; i--) { AdjustDown(a, size, i); } //O(N*log(N)) int end = size - 1; while (end) { //1.先交换 Swap(&a[0], &a[end]); //2.再调整，选出当前大小的数组中最小数 AdjustDown(a, end, 0); end--; } }
4、堆排序测试
我们建的是小堆，因此最终排的是降序。
*** 本篇结束 ***
