动画

实现

堆的定义

堆其实是一种特殊的树。只要满足这两点，它就是一个堆。

• 堆是一个完全二叉树。
  完全二叉树：除了最后一层，其他层的节点个数都是满的，最后一层的节点都靠左排列。
• 堆中每一个节点的值都必须大于等于（或小于等于）其子树中每个节点的值。
  也可以说：堆中每个节点的值都大于等于（或者小于等于）其左右子节点的值。这两种表述是等价的。

对于每个节点的值都大于等于子树中每个节点值的堆，我们叫作大顶堆。
对于每个节点的值都小于等于子树中每个节点值的堆，我们叫作小顶堆。

思想

1. 将初始待排序关键字序列 (R1, R2 .... Rn) 构建成大顶堆，此堆为初始的无序区
2. 将堆顶元素 R[1] 与最后一个元素 R[n] 交换，此时得到新的无序区 (R1, R2, ..... Rn-1) 和新的有序区(Rn) ，且满足 R[1, 2 ... n-1] <= R[n]。
3. 由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1, R2 ...... Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1, R2 .... Rn-2)和新的有序区 (Rn-1, Rn)。不断重复此过程，直到有序区的元素个数为 n - 1，则整个排序过程完成。

   实现

   ```javascript const array = [3, 44, 38, 5, 47, 15, 36, 26, 1, 27, 46, 4, 19, 50, 48];

// 堆排序 const heapSort = (arr) => { const len = arr.length; // 初始化最大堆 for (let i = Math.floor(len / 2); i >= 0; i—) { heapify(arr, i, len); } // 将堆的第一项放到最后，再进行排序 for (let i = len - 1; i > 0; i—) { // 根节点与最后一个节点交换 swap(arr, 0, i); // 从根节点开始调整，并且最后一个结点已经为当前最大值，不需要再参与比较，所以第三个参数为 i，即比较到最后一个结点前一个即可 heapify(arr, 0, i); } }

// 堆化：将 i 元素与左右子节点比较 const heapify = (arr, i, end) => { let left = 2 i + 1; let right = 2 i + 2; let largest = i; if (left < end && arr[largest] < arr[left]) { largest = left; } if (right < end && arr[largest] < arr[right]) { largest = right; } if (largest !== i) { swap(arr, i, largest); heapify(arr, largest, end); } }

const swap = (arr, i, j) => { const tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; }

heapSort(array); console.log(array); ``` 堆化的函数 heapify 使用的递归，可以将其改成 for 循环。当数组长度很长时，消耗的性能会少一些

分析

• 第一，堆排序是原地排序算法吗 ？
  整个堆排序的过程，都只需要极个别临时存储空间，所以堆排序是原地排序算法。
• 第二，堆排序是稳定的排序算法吗 ？
  因为在排序的过程，存在将堆的最后一个节点跟堆顶节点互换的操作，所以就有可能改变值相同数据的原始相对顺序。
  所以，堆排序是不稳定的排序算法。
• 第三，堆排序的时间复杂度是多少 ？
  堆排序包括建堆和排序两个操作，建堆过程的时间复杂度是 O(n)，排序过程的时间复杂度是 O(nlogn)，所以，堆排序整体的时间复杂度是 O(nlogn)。
  最佳情况：T(n) = O(nlogn)。
  最差情况：T(n) = O(nlogn)。
  平均情况：T(n) = O(nlogn)。