堆排序详细理解

目录

一、前备知识

二、建堆

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 向上调整算法建堆

思路：

1. 单一的一个结点可以看成一个堆
2. 后续的所有结点都可以看作是插入结点

所以只需要循环插入所有后续结点即可

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 常见问题 

• 为什么建堆后依然还要排序？

        大堆/小堆的定义注定了堆仅仅能保证父节点大于孩子结点，无法保证孩子结点按照大于/小于的次序严格排列！！！

• 升序建小堆，降序建大堆的思路是否可行？

1. 升序建小堆：首先对 n 个数建小堆，选出最小的数，接着对剩下的 n-1 个数建小堆，选出第二小的数，不断重复上述过程。若用向上调整算法可行但时间复杂度太高，若使用向下调整算法时，对n-1个调整就会发现：原先的孩子父亲关系全乱，不可行。
2. 降序建大堆：首先对 n 个数建小堆，选出最小的数，接着对剩下的 n-1 个数建大堆，选出第二大的数，不断重复上述过程。使用向下调整算法时，对n-1个调整就会发现：原先的孩子父亲关系全乱，不可行。

3.2 思路

1. 本质上是堆删除的思路。利用堆的特性，无论是大堆还是小堆，根节点的值一定是最大/小的数。这样每进行一次调整，就会选择出最小/大，次小/大......便可以实现排序。
2. 为了防止出现父子关系乱序的问题，将每次找到的最值放在堆的末位置，对前n-1个元素进行向下调整，便可以完美解决排序问题
3. 由此可以总结：升序建大堆，降序建小堆。

由此，我们可以归纳出堆排序算法的步骤：

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个元素}
}