堆排序是一种基于比较的排序技术，它利用了二叉堆这种数据结构进行排序。二叉堆是一个完全二叉树，可以被看作是一个数组对象。堆分为最大堆和最小堆两种类型。最大堆中的每个父节点的元素值都大于或等于其所有子节点的元素值；最小堆则相反。
本章将详细介绍如何使用 JavaScript 实现堆排序算法，包括以下内容：
- 堆的基本概念
- 最大堆和最小堆的实现
- 建立堆的过程
- 堆排序算法的实现步骤
- 示例代码解析
- 时间复杂度分析
- 优化建议
堆的基本概念
完全二叉树
完全二叉树是一种特殊的二叉树，除了最后一层外，每一层上的结点数都达到最大值，并且最后一层上的结点都尽可能靠左排列。这种结构使得完全二叉树可以用一个数组来表示，数组的索引对应于树的节点。
数组表示法
由于完全二叉树的特性，可以使用数组来表示一个堆。数组的第 i 个元素对应于完全二叉树的第 i 个节点。对于数组中的任意元素 A[i]：
- 如果 i > 0，则 A[i] 的父节点为 A[Math.floor((i-1)/2)]
- 如果 2i+1 < 数组长度，则 A[i] 的左孩子为 A[2i+1]
- 如果 2i+2 < 数组长度，则 A[i] 的右孩子为 A[2i+2]
最大堆和最小堆的实现
最大堆
最大堆要求父节点的值大于等于其左右子节点的值。因此，在构建最大堆时，需要确保从根节点到叶节点的路径上，每个节点的值都不小于其子节点的值。
最小堆
最小堆与最大堆相反，它要求父节点的值小于等于其左右子节点的值。在构建最小堆时，需要保证从根节点到叶节点的路径上，每个节点的值都不大于其子节点的值。
建立堆的过程
建立堆的过程包括两个主要步骤：初始化和调整。首先，将原始数据构建成一个堆；然后通过不断调整来保证堆的性质。
初始化
对于给定的一组数据，可以先将其放入一个数组中，然后从最后一个非叶子节点开始向上调整，以确保每个节点都满足堆的性质。
调整
调整过程是通过“下沉”操作完成的。当某个节点违反了堆的性质时（例如在最大堆中，某个节点的值小于其子节点的值），需要将该节点与其较大的子节点交换位置，直到该节点满足堆的性质为止。
堆排序算法的实现步骤
堆排序算法主要包括以下几步：
- 建堆：将待排序的数组构造成一个最大堆。
- 交换根节点与末尾节点：将堆顶元素（最大值）与堆底元素交换，然后将堆的大小减一，重新调整剩余部分成为最大堆。
- 重复步骤 2：重复上述过程，直到堆的大小为 1，此时数组已经排好序。
示例代码解析
以下是使用 JavaScript 实现的最大堆排序示例代码：
// www.javascriptcn.com code example
function heapSort(arr) {
// 建立最大堆
buildMaxHeap(arr);
for (let i = arr.length - 1; i >= 0; i--) {
// 将堆顶元素与末尾元素交换
[arr[0], arr[i]] = [arr[i], arr[0]];
// 重新调整剩余部分为最大堆
maxHeapify(arr, 0, i);
}
}
function buildMaxHeap(arr) {
const length = arr.length;
// 从最后一个非叶子节点开始调整
for (let i = Math.floor(length / 2) - 1; i >= 0; i--) {
maxHeapify(arr, i, length);
}
}
function maxHeapify(arr, index, heapSize) {
let largest = index;
const left = 2 * index + 1;
const right = 2 * index + 2;
if (left < heapSize && arr[left] > arr[largest]) {
largest = left;
}
if (right < heapSize && arr[right] > arr[largest]) {
largest = right;
}
if (largest !== index) {
[arr[index], arr[largest]] = [arr[largest], arr[index]];
maxHeapify(arr, largest, heapSize);
}
}时间复杂度分析
堆排序的时间复杂度为 O(n log n)，其中 n 是数组的长度。这是因为建堆的过程需要 O(n) 的时间，而每次调整堆需要 O(log n) 的时间，总共需要进行 n-1 次调整。
优化建议
虽然堆排序的时间复杂度较低，但在实际应用中，对于较小的数据集，快速排序等其他算法可能更快。此外，如果内存允许，可以考虑使用计数排序、基数排序等线性时间复杂度的排序方法，特别是当数据范围有限时。对于非常大的数据集，可以考虑并行处理，提高排序效率。