堆排序是一种基于比较的排序算法，它通过构造一个大顶堆或小顶堆来实现排序。在本文中，我们将深入探讨堆排序的概念、工作原理以及如何在JavaScript中实现这一算法，同时关注如何保存比较结果。
让我们了解什么是完全二叉树。在计算机科学中，完全二叉树是一种特殊的二叉树结构，其中除了最后一层外，每一层都被完全填满，且所有的结点都尽可能地靠左放置。最后一层的所有结点都集中在左边。例如，一个包含n个结点的完全二叉树的高度最多是log2(n)+1。
在堆排序中，我们通常使用大顶堆或小顶堆。大顶堆保证每个父结点的值都大于或等于其子结点的值，而小顶堆则相反，父结点的值小于或等于子结点的值。在这个场景下，“双亲节点”指的是当前结点的父结点，其索引可以通过公式i / 2计算得出。同样，一个结点的“子女”是它的直接子结点，它们的索引为2i和2i+1。
接下来，我们来逐步解析堆排序的过程：
1. **建堆**：从最后一个非叶子节点开始，自底向上遍历树，对每个结点进行调整，使其满足大顶堆或小顶堆的性质。这个过程也被称为“下沉”。
2. **交换与缩小堆**：将堆顶元素（最大或最小元素）与最后一个元素交换位置，然后删除最后一个元素。接着，对剩下的元素重新调整为堆，重复此过程直到堆的大小为1。
3. **保存比较结果**：在堆排序过程中，每次比较都会影响到堆的结构，因此我们可以记录这些比较结果，以了解排序过程中的关系变化。例如，我们可以创建一个二维数组来存储每一对被比较的元素及其比较结果（大于、小于或等于）。
在JavaScript中，实现堆排序并保存比较结果，你可以使用数组作为数据结构，如下所示：
```javascript
function heapSort(arr, compareFn) {
const comparisons = [];
let n = arr.length;
// 建堆
for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
heapify(arr, n, i, comparisons);
}
// 交换并缩小堆
for (let i = n - 1; i > 0; i--) {
[arr[0], arr[i]] = [arr[i], arr[0]]; // 交换元素
comparisons.push({ left: arr[i], right: arr[0], result: compareFn(arr[0], arr[i]) });
heapify(arr, i, 0, comparisons);
}
return { sortedArray: arr, comparisons: comparisons };
}
function heapify(arr, n, i, comparisons) {
let largest = i;
let left = 2 * i + 1;
let right = 2 * i + 2;
if (left < n && compareFn(arr[left], arr[largest]) > 0) {
largest = left;
comparisons.push({ left: arr[left], right: arr[largest], result: compareFn(arr[left], arr[largest]) });
}
if (right < n && compareFn(arr[right], arr[largest]) > 0) {
largest = right;
comparisons.push({ left: arr[right], right: arr[largest], result: compareFn(arr[right], arr[largest]) });
}
if (largest !== i) {
[arr[i], arr[largest]] = [arr[largest], arr[i]];
heapify(arr, n, largest, comparisons);
}
}
```
这段代码中，`heapSort`函数接收一个数组和一个比较函数，返回一个对象，包含已排序的数组和比较结果。`heapify`函数用于维护堆的性质。在每次比较时，我们都会向`comparisons`数组添加比较记录。
在实际应用中，你可能会在`compareFn`中使用JavaScript的内置`compare`函数，如`>`, `<`, 或 `===`，或者自定义比较逻辑，以适应不同的需求。
以上就是关于堆排序的基本概念、实现方法以及如何在JavaScript中保存比较结果的详细介绍。通过这个过程，我们可以高效地对数据进行排序，并跟踪整个排序过程中元素之间的比较情况。
