堆排序详细理解
目录
一、前备知识
二、建堆
2.2.1 向上调整算法建堆
2.2.2 向下调整算法建堆
三、排序
3.1 常见问题
3.2 思路
3.3 源码
一、前备知识
详细图解请点击：二叉树的顺序实现-堆-CSDN博客
本文只附上向上/向下调整算法的源码
//交换
void Swap(int* p, int* q)
{int tmp = *p;*p = *q;*q = tmp;
}
//向下调整算法
void AdjustDown(int* a, int n, int parent)
{//左孩子的下标int child = parent * 2 + 1;while (child<n){//找到两个孩子中较小的孩子-假设法if (child + 1 < n && a[child + 1] < a[child]){child++;}if (a[parent] > a[child]){Swap(&a[parent], &a[child]);parent = child;child = parent * 2 + 1;}else{break;}}
}
//向上调整算法
void AdjustUp(int* 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.2.1 向上调整算法建堆
思路：
- 单一的一个结点可以看成一个堆
- 后续的所有结点都可以看作是插入结点
所以只需要循环插入所有后续结点即可
void BuildHeap1(int* a, int n)
{//把根节点看作是堆，剩下的结点看作插入结点，开始依次插入for (int i = 1; i < n; i++){AdjustUp(a, i);}
}2.2.2 向下调整算法建堆
错误思路：
向下调整算法要求左右子树必须为大/小堆，所以从根节点开始结点开始建堆的做法是错误的
正确思路：
上文说：单一的一个结点可以看成一个堆。所以从最后一个叶子节点的父节点开始向下调整，不断循环所有父节点，就可以保证他的左右子树都是堆。
void BuildHeap2(int* a, int n)
{//从最后一个叶子结点的父结点开始调for (int i = ((n - 1) - 1) / 2; i >= 0; i--){AdjustDown(a, n, i);}
}三、排序
3.1 常见问题
- 为什么建堆后依然还要排序？
大堆/小堆的定义注定了堆仅仅能保证父节点大于孩子结点，无法保证孩子结点按照大于/小于的次序严格排列！！！
- 升序建小堆，降序建大堆的思路是否可行？
- 升序建小堆：首先对 n 个数建小堆，选出最小的数，接着对剩下的 n-1 个数建小堆，选出第二小的数，不断重复上述过程。若用向上调整算法可行但时间复杂度太高，若使用向下调整算法时，对n-1个调整就会发现：原先的孩子父亲关系全乱，不可行。
- 降序建大堆：首先对 n 个数建小堆，选出最小的数，接着对剩下的 n-1 个数建大堆，选出第二大的数，不断重复上述过程。使用向下调整算法时，对n-1个调整就会发现：原先的孩子父亲关系全乱，不可行。
3.2 思路
- 本质上是堆删除的思路。利用堆的特性，无论是大堆还是小堆，根节点的值一定是最大/小的数。这样每进行一次调整，就会选择出最小/大，次小/大......便可以实现排序。
- 为了防止出现父子关系乱序的问题，将每次找到的最值放在堆的末位置，对前n-1个元素进行向下调整，便可以完美解决排序问题
- 由此可以总结：升序建大堆，降序建小堆。
由此，我们可以归纳出堆排序算法的步骤：
1. 把无序数组构建成二叉堆。
2. 循环删除堆顶元素，移到数组尾部，调节堆产生新的堆顶。
3.3 源码
//降序建小堆
void HeapSortDown(int* a, int n)
{//建小堆for (int i = ((n - 1) - 1) / 2; i >= 0; i--){AdjustDown(a, n, i);}//排序int end = n - 1; //定位数组最后一个位置while (end > 0){Swap(&a[0], &a[end]); // 将堆顶元素和堆中最后一个元素交换，把最大的数(堆顶)放到最后AdjustDown(a, end, 0);end--; // 调整前n-1个元素}
}