经典排序算法之堆排序详解|c++代码实现|什么是堆排序|如何代码实现堆排序_c++堆排序

引言

排序算法c++实现系列第7弹——堆排序。

建议先去b站观看该视频，有声音有动态演示步骤，效果更佳 —— 【从堆的定义到优先队列、堆排序】 10分钟看懂必考的数据结构——堆哔哩哔哩bilibili，看完视频大概了解了过程后，再回来看文章，事半功倍！

这是一篇耗费了一整个下午才写出来的文章，除了部分显而易见的知识点外都尽可能详细的解释或者证明了。所以，如果uu觉得这篇文章对你有所帮助和启发，也麻烦点个赞和收藏了。另外，文章末尾也有其他排序算法的实现，后续也还会继续更新的算法，有兴趣的佳人也可以点个关注，以防走丢咯！那样的话，鄙人感激涕零（呜呜呜呜呜呜呜呜

什么是完全二叉树

完全二叉树是一种特殊的二叉树，它具有以下性质：

1. 定义： 完全二叉树是一种二叉树，其中除了最后一层外，每一层上的节点都有两个子节点，并且最后一层上的节点都集中在树的左侧。也就是说，最后一层上的节点从左到右依次填满，先填左边后填右边，缺少的部分在右边不填。

2. 性质：

   • 完全二叉树的高度为(h)时，其最多有(2^h - 1)个节点。

   • 在完全二叉树中，第(i)层的节点数最多为(2^{i-1})个，其中(i >= 1)。

   • 如果按照层次顺序从上到下、从左到右编号，那么对于任意一个节点编号为(i)，其左子节点编号为(2i)，右子节点编号为(2i + 1)，此时节点从1开始编号。如果节点从0开始编号，那么有对于任意一个节点编号为(i)，其左子节点编号为(2i + 1)，右子节点编号为(2i + 2)，则对于任意一个非根节点x，其父节点为 （x - 1）/ 2。

     在本文以下篇幅和代码中，均从0开始编号。

     由于完全二叉树的此性质，堆的实现可以通过数组来完成，这种实现方式称为数组表示法。

堆

什么是堆

堆（Heap）这种数据结构是完全二叉树的一个重要应用，它一种特殊的完全二叉树，用于实现优先队列（STL中的priority_queue）等数据结构。对于堆，由最大堆和最小堆：

• 最大堆，父节点的值大于等于其两个子节点的值

• 最小堆，父节点的值小于等于其两个子节点的值

上滤和下滤

在堆中，有两个极为重要的操作——上滤和下滤：

• 上滤，多用于在堆中插入新元素。它的基本思想是先将新元素插入到堆的末尾，然后将新元素依次与其父节点进行比较，并在必要时交换位置，直到满足堆的性质为止。对于最小堆，上滤操作是将新元素与父节点比较，如果新元素小于其父节点，则交换位置，直到新元素不小于其父节点或者成为根节点为止。对于最大堆，上滤操作是将新元素与父节点比较，如果新元素大于其父节点，则交换位置，直到新元素不大于其父节点或者成为根节点为止。

• 下滤，多用于在堆中删除堆顶元素。它的基本思想是将堆的末尾元素移动到堆顶，然后将堆顶元素依次与其子节点进行比较，并在必要时交换位置，直到满足堆的性质为止。对于最小堆，下滤操作是将堆顶元素与其较小的子节点进行比较，如果堆顶元素大于其较小的子节点，则交换位置，直到堆顶元素不大于其子节点或者成为叶子节点为止。对于最大堆，下滤操作是将堆顶元素与其较大的子节点进行比较，如果堆顶元素小于其较大的子节点，则交换位置，直到堆顶元素不小于其子节点或者成为叶子节点为止。

通过上滤操作和下滤操作，保证了在堆中插入和删除元素后，堆仍然保持堆的性质。最大堆/最小堆，上滤/下滤都不是特别难的概念，但对于堆排序学习而言却是很重要的。所以如果有不理解的uu，可以边看本文开篇的视频推荐边看以上介绍。

如何建堆

构建堆的方法有两种常见的实现方式：自顶向下和自底向上，二者都可以实现最大堆和最小堆的建立。

1. 自顶向下建堆：

   • 自顶向下从根节点开始逐级向下调整堆的结构，使得整个堆满足堆的性质。

   • 自顶向下建堆的具体步骤如下：

     1. 依次输入元素，并将其放在当前堆的最后一个。

     2. 每次输入一个新的元素后，便从根节点开始，依次对每个节点进行下滤操作（即调整堆），将当前节点与其子节点比较，如果不满足堆的性质则进行交换，直到当前节点成为叶子节点或者满足堆的性质为止。

     3. 重复步骤2，直到对所有节点完成下滤操作，最终得到一个满足堆的性质的堆。

   • 时间复杂度为O(nlogn) —— 总共n个元素，每个元素都要进行下滤操作。

2. 自底向上建堆：

   • 自底向上建堆是一种迭代的方法，它从最后一个非叶子节点开始，逐级向上调整堆的结构，使得整个堆满足堆的性质。

   • 自底向上建堆的过程是一个自底向上的迭代过程。具体步骤如下：

     1. 先将一组无序数据存储到堆中，在代码中就是最初的存储这组数据的数组。

     2. 从最后一个非叶子节点（下标为( arr.len/2 - 1)）开始，依次对每个非叶子节点（也就是每个父节点）进行下滤操作（即调整堆），将当前节点与其子节点比较，如果不满足堆的性质则进行交换，直到当前节点成为根节点或者满足堆的性质为止。

        • 这里说明为什么下标为( arr.len/2 - 1)的元素是最后一个根节点（非叶子节点），首先，明确一件事：最后一个根节点也就是最后一个叶子节点的父节点。而从前面的介绍中，我们知道了 “如果节点从0开始编号，那么有对于任意一个节点编号为(i)，其左子节点编号为(2i + 1)，右子节点编号为(2i + 2)，则对于任意一个非根节点x，其父节点为 （x - 1）/ 2。”  讲到这，相信大家都已经 get 到了其中的玄机 —— 最后一个叶子节点的下标应为 arr.len - 1，所以其父节点的下标自然为 （(arr.len - 1 - 1) / 2），也就是arr.len/2 - 1。

     3. 重复步骤2，直到对所有非叶子节点完成操作，最终得到一个满足堆的性质的堆。

   • 时间复杂度为O(n) —— 可以假设是一个满二叉树同时每个根节点都下滤最多的次数（到叶子节点） —— 这样求的结果理论上肯定是比真实情况下大的，用高中学的 等差-等比数列求和公式（错位相减）求解可以得到时间复杂度为O(n)

堆排序

堆排序（Heap Sort）是一种利用堆数据结构实现的排序算法，其基本思想是先将待排序数组构建成一个堆，然后反复从堆中取出最值（根节点），并进行交换和调整，最终得到一个有序数组。

复杂度分析

堆排序的总时间复杂度为O(nlogn)，不需要额外的辅助空间，空间复杂度为O(1)。但由于相等元素的相对位置可能会改变，因此堆排序是一种不稳定的排序算法。

具体步骤

堆排序的实现步骤如下（建议参考着推荐视频一起看）：

1. 建堆：将待排序数组构建成一个堆。根据数组元素构建最大堆或最小堆（通常都用最大堆），通常使用自底向上的方式进行构建（复杂度小），代码中使用自底向上建最大堆。

2. 调整堆：将堆顶元素与堆尾元素交换，并将堆的大小减一（相当于原本倒数第二个元素

   ---

   成为了堆尾元素），然后对堆进行下滤调整，使其继续保持为最大堆。

3. 重复步骤2：重复步骤2，直到堆的大小减少到1，此时数组已经排序完成。

代码实现

#include<bits/stdc++.h>
using namespace std;
template<typename T>
void max_heapify(T arr[], int start, int end) {
	int dad = start;
	int son = dad * 2 + 1;
	while (son <= end) { // 保证节点在有效范围内 
		if ((son < end) && arr[son] < arr[son + 1]) { //有右节点同时右节点比左节点大 
			son++;  // 让i指向子节点里最大的 
		}
		if (arr[dad] > arr[son]) {
		// 这是一个需要好好理解的break：我们从最后一个非叶子节点自底向上开始迭代的，
		// 也就是说在当前父节点下的子树是已经成为了最大堆的，所以当此处的父节点值大于其两个子节点时是可以直接break的 
			break;
		} else {
			swap(arr[dad], arr[son]);
			// 更新根节点和左子节点 
			dad = son;
			son = 2 * dad + 1;
		}
	}
}
template<typename T>
void heap_sort(T arr[], int len) {
	int i = len / 2 - 1;
	while (i >= 0) { // 遍历每一个父节点以构造最大堆 
		max_heapify(arr, i, len - 1);
		i--;
	}
	for (int i = len - 1; i >= 0; i--) { // 利用最大堆开始排序 
		swap(arr[i], arr[0]);
		max_heapify(arr, 0, i - 1); // 调整新的堆使其成为最大堆 
	}
}
int main() {
 
	int arr[] = {61, 17, 29, 22, 34, 60, 72, 21, 50, 1, 62};
	int len = (int) sizeof(arr) / sizeof(*arr);
	heap_sort(arr, len);
	for (int i = 0; i < len; i++) {
		cout << arr[i] << " ";
	}
	cout << endl;
	float arrf[] = {17.5, 19.1, 0.6, 1.9, 10.5, 12.4, 3.8, 19.7, 1.5, 25.4, 28.6, 4.4, 23.7, 5.4};
	int lenf = sizeof(arrf) / sizeof(*arrf);
	heap_sort(arrf, lenf);
	for (int i = 0; i < lenf; i++) {
		cout << arrf[i] << " ";
	}
 
	return 0;
}

运行结果演示

其他排序算法实现

十大经典排序算法复杂度、应用场景总结 | 插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序、桶排序、计数排序-CSDN博客

经典排序算法之基数排序详解|c++代码实现|简单易懂-CSDN博客

经典排序算法之桶排序详解|c++代码实现|简单易懂-CSDN博客

经典排序算法之计数排序|c++代码实现-CSDN博客

 经典排序算法之快速排序|c++代码实现|什么是快速排序|如何代码实现快速排序-CSDN博客

经典排序算法之归并排序|递归和迭代法代码均提供|c++代码实现|什么是归并排序|如何代码实现-CSDN博客

经典排序算法之希尔排序|c++代码实现||什么是希尔排序|如何代码实现-CSDN博客

经典排序算法之插入排序|c++实现|什么是插入排序|如何代码实现-CSDN博客

排序算法之选择排序|c++实现-CSDN博客

经典排序算法之冒泡排序|c++代码实现-CSDN博客