堆排序

前言

堆排序实质上是选择排序的一种优化：

• 选择排序：O(n^2)
  将原始数据集合分为两部分 —— 有序区域和无序区，在无序区中寻找最小值，然后与无序区中第一个进行交换位置，这样不断的缩小无序区大小。
• 堆排序：O(nlog2^n)
  使用无序区创建大根堆，然后将根元素与最后一个元素交换位置，相当于不断地找最大元素，将它与无序区最后一个元素交换位置。同样，如果换作小根堆，则可以与选择排序相对应。（选择排序同理）
  （堆排序主要优化了选择过程的效率）

步骤

1. 构建大根堆
2. 取根（将根与堆中的最后一个元素做交换）
3. 重新确定新堆的索引范围，调整堆

调整堆

/**
 * 从 index 开始检查，并保证该位置之下的所有子树均为最大堆
 * @heapSize 堆的大小（元素个数）
 **/
function maxHeapify(arr, index, heapSize) {
  let iMax = index, iLeft = 2 * index + 1, 2 * (index + 1)
  if(iLeft < heapSize && arr[index] < arr[iLeft]) {
    iMax = iLeft
  }
  
  if(iRight < heapSize && arr[iMax] < arr[iRight]) {
    iMax = iRight
  }

  if(iMax !== index) {
    swap(arr, iMax, index)
    maxHeapify(arr, iMax, heapSize)
  }
}

arr 表示当前堆的数据集合，index 为当前子树的根，执行结果会保持当前堆的大根堆性质。heapSize 表示当前堆的大小。
在不超出堆大小的前提下，调整当前子树的三个节点，保证它为一个大根堆，同时因为如果发生了调整，可能会导致该子树的大根堆性质遭到破坏，因此需要对该子树进行递归检查，直至超出堆的总大小（也可以理解为检查到叶子结点了）或者该子树根本不需要调整。

构建大根堆

/**
 *  将初始的无序数组调整为大根堆, 最小堆的建堆函数相同
 **/
function buildMaxHeap(arr, heapSize) {
  let iParent = Math.floor((heapSize - 1) / 2)
  for(let i = iParent; i >= 0; i--) {
    maxHeapify(arr, i, heapSize)
  }
}

由于我们的 maxHeapify 函数在调整堆的时候，能够保证被操作的每一棵以下所有子树都保持大根堆的性质，因此我们只要自下而上得执行 maxHeapify 函数，这样在往上走的时候，可以保证子树是最大堆，也满足了 maxHeapify 的逻辑要求。那么如何找到完全二叉树的最底层呢？

拓展

层序构建完全二叉树索引于父子之间的关系：
从 1 开始编号

• Parent(i) = floor(i/2)，i 的父节点下标
• Left(i) = 2i，i 的左子节点下标
• Right(i) = 2i + 1，i 的右子节点下标

从 0 开始编号

• Parent(i) = floor((i-1)/2)，i 的父节点下标
• Left(i) = 2i + 1，i 的左子节点下标
• Right(i) = 2(i + 1)，i 的右子节点下标

关于完全二叉树的一些基本性质：

1. 二叉树的第 i 层上最多有 2^(i-1) 个结点
2. 在一颗深度为 k 的二叉树中，最多有 2^k - 1 个元素，最少有 k 个结点（斜树或类斜树）
3. 在一颗二叉树中，如果拥有两个孩子（2度）的子树个数为n，则叶子数为 n + 1
4. 在一棵从 1 开始按照层序编号的完全叉树中：（总结点数目为 n）
   4.1. 如果 i > 1，则结点 i 的双亲的编号为 floor(i/2)
   4.2. 如果 2i <= n, 则 i 的左孩子编号为 2i，否则没有左孩子
   4.3. 如果 2i + 1 <= n, 则 i 的右孩子编号为 2i + 1，否则没有右孩子

1. 由以上第三点可以推出，当树中不存在一度结点时，整棵树完全由二度结点和叶子组成，也就是说，总结点量 = 2n + 1，由此可以计算出共有 (总量 - 1) / 2 个二度结点, 再减一则为其索引；当存在一度结点时，总结点量= 2n + 2，二度结点数 = 总量/2 - 1，而其索引则为 总量/2 - 1 - 1，即 (总量-1) / 2。如果笼统的使用后者，会导致前者不在考虑范围内，不过也是多计算了一次叶子，依然符合调整堆的核心函数要求。
2. 或者由 4.2 推出，当 2i === n 时，i 一定是最后一个拥有左孩子的结点，因此，n / 2 应当是最后一个子树; 可惜，在 Zero-Based 的情况下，4.2 这个定理不成立，因此不介入讨论范围内（数据结构本科课本则是使用 One-Based 来表述的伪码，因此和这里有所出入）

由此可得，索引最大值 (heapSize - 1)/2 即是完全二叉树最后一颗子树根所在的位置。 然后使用倒序遍历则可以遍历完树中所有的子树。

入口函数

function heapSort (arr, heapSize) {
  buildMaxHeap(arr, heapSize)
  for(let i = heapSize - 1; i > 0; i--) {
    swap(arr, 0, i) // 这里的 i 表示下标
    maxHeapify(arr, 0, i) // 这里的 i 表示堆大小
  }
}

关于小根堆的思考

在这里构建小根堆和大根堆的逻辑无二，问题就在于入口函数上。大根堆的逻辑是在创建好大根堆之后，将根节点（0）与当前堆的最后一个元素交换，然后不断缩小 heapSize，这样倒序剪叶子, 不会影响之前已经调整好的堆结构。

如果使用小根堆的话，那么在建堆完毕之后，第一个元素就是最小的元素，如果正序缩小范围的话，树结构会被破坏，需要重写调整堆结构的核心子程序。当然，如果是倒序排序的话，小根堆就方便多了。