堆排序算法详解：原理、实现步骤及C++代码示例
堆排序算法详解：原理、实现步骤及C++代码示例
堆排序是一种利用堆数据结构实现的排序算法，其基本思想是先将待排序数组构建成一个堆，然后反复从堆中取出最值（根节点），并进行交换和调整，最终得到一个有序数组。本文将详细介绍堆排序的原理、实现步骤，并提供C++代码示例。
引言
排序算法c++实现系列第7弹——堆排序。
什么是完全二叉树
完全二叉树是一种特殊的二叉树，它具有以下性质：
定义： 完全二叉树是一种二叉树，其中除了最后一层外，每一层上的节点都有两个子节点，并且最后一层上的节点都集中在树的左侧。也就是说，最后一层上的节点从左到右依次填满，先填左边后填右边，缺少的部分在右边不填。
性质：
完全二叉树的高度为(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）等数据结构。对于堆，由最大堆和最小堆：
最大堆，父节点的值大于等于其两个子节点的值
最小堆，父节点的值小于等于其两个子节点的值
上滤和下滤
在堆中，有两个极为重要的操作——上滤和下滤：
上滤，多用于在堆中插入新元素。它的基本思想是先将新元素插入到堆的末尾，然后将新元素依次与其父节点进行比较，并在必要时交换位置，直到满足堆的性质为止。对于最小堆，上滤操作是将新元素与父节点比较，如果新元素小于其父节点，则交换位置，直到新元素不小于其父节点或者成为根节点为止。对于最大堆，上滤操作是将新元素与父节点比较，如果新元素大于其父节点，则交换位置，直到新元素不大于其父节点或者成为根节点为止。
下滤，多用于在堆中删除堆顶元素。它的基本思想是将堆的末尾元素移动到堆顶，然后将堆顶元素依次与其子节点进行比较，并在必要时交换位置，直到满足堆的性质为止。对于最小堆，下滤操作是将堆顶元素与其较小的子节点进行比较，如果堆顶元素大于其较小的子节点，则交换位置，直到堆顶元素不大于其子节点或者成为叶子节点为止。对于最大堆，下滤操作是将堆顶元素与其较大的子节点进行比较，如果堆顶元素小于其较大的子节点，则交换位置，直到堆顶元素不小于其子节点或者成为叶子节点为止。
通过上滤操作和下滤操作，保证了在堆中插入和删除元素后，堆仍然保持堆的性质。最大堆/最小堆，上滤/下滤都不是特别难的概念，但对于堆排序学习而言却是很重要的。
如何建堆
构建堆的方法有两种常见的实现方式：自顶向下和自底向上，二者都可以实现最大堆和最小堆的建立。
自顶向下建堆：
自顶向下从根节点开始逐级向下调整堆的结构，使得整个堆满足堆的性质。
自顶向下建堆的具体步骤如下：
依次输入元素，并将其放在当前堆的最后一个。
每次输入一个新的元素后，便从根节点开始，依次对每个节点进行上滤操作（即调整堆），将当前节点与其子节点比较，如果不满足堆的性质则进行交换，直到当前节点成为叶子节点或者满足堆的性质为止。
重复步骤2，直到对所有节点完成下滤操作，最终得到一个满足堆的性质的堆。
时间复杂度为O(
nlogn
) —— 总共n个元素，每个元素都要进行下滤操作。
自顶向下建堆其实就是每次在堆尾插入新元素，再通过上滤调整成堆。
自底向上建堆：
自底向上建堆是一种迭代的方法，它从最后一个非叶子节点开始，逐级向上调整堆的结构，使得整个堆满足堆的性质。
自底向上建堆的过程是一个自底向上的迭代过程。具体步骤如下：
先将一组无序数据存储到堆中，在代码中就是最初的存储这组数据的数组。
从最后一个非叶子节点（下标为(
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
。
重复步骤2，直到对所有非叶子节点完成操作，最终得到一个满足堆的性质的堆。
时间复杂度为O(
n
) —— 可以假设是一个满二叉树同时每个根节点都下滤最多的次数（到叶子节点） —— 这样求的结果理论上肯定是比真实情况下大的，用高中学的 等差-等比数列求和公式（错位相减）求解可以得到时间复杂度为O(n)
堆排序
堆排序（Heap Sort）是一种利用堆数据结构实现的排序算法，其基本思想是先将待排序数组构建成一个堆，然后反复从堆中取出最值（根节点），并进行交换和调整，最终得到一个有序数组。
复杂度分析
堆排序的总时间复杂度为O(
nlogn
)，不需要额外的辅助空间，空间复杂度为O(1)。但由于相等元素的相对位置可能会改变，因此堆排序是一种不稳定的排序算法。
具体步骤
堆排序的实现步骤如下（建议参考着推荐视频一起看）：
建堆：将待排序数组构建成一个堆。根据数组元素构建最大堆或最小堆（通常都用最大堆），通常使用自底向上的方式进行构建（复杂度小），代码中使用自底向上建最大堆。
调整堆：将堆顶元素与堆尾元素交换，并将堆的大小减一（相当于原本倒数第二个元素
成为了堆尾元素），然后对堆进行下滤调整，使其继续保持为最大堆。
重复步骤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博客