排序算法-3（javascript） 堆排序的实现

前面我们已经讲过二叉堆是啥了，然后也晓得最大堆和最小堆的实现。（不晓得的同学，传送门走起：https://www.jianshu.com/p/d79e39430cd2）

一般数组排序，我们都是默认按从小到大排，所以这要用到的最大堆（如果是按从大到小，那么同理就用最小堆实现）。所以后面说到堆都是特指最大堆哈。

先看下最大堆的实现：

/*
  二叉堆的最大堆代码实现
*/

// 根据子节点下标的奇偶性，来获取对应父节点的下标
function getParentIndex(childIndex) {
  let parentIndex = 0;
  if(childIndex % 2 === 0) {
    parentIndex = (childIndex - 2) / 2  // 如果是右节点，父节点的下标
  }else{
    parentIndex = (childIndex - 1) / 2  // 如果是左节点，父节点的下标
  }
  return parentIndex;
}


// 最大堆上浮(一般对应插入操作)
function upAdjust(arr) {
  let childIndex = arr.length -1; // 初始子节点的下标
  parentIndex = getParentIndex(childIndex)
  let temp = arr[childIndex]  // 子节点值
  while((childIndex > 0) && (temp > arr[parentIndex])) {
    arr[childIndex] = arr[parentIndex]
    childIndex = parentIndex
    // 根据子节点下标的奇偶性，来获取对应父节点的下标
    parentIndex = getParentIndex(childIndex)
  }
  arr[childIndex] = temp
  return arr;
}

const testArr1 = upAdjust([4,2,9,1,7,8,36])
console.log(testArr1); // [ 36, 2, 4, 1, 7, 8, 9 ]


/**
 * @description 二叉堆下沉（最大堆）
 * @param arr: 待调整的二叉堆
 * @param parentIndex: 要下沉的父节点位置
 * @param length: 堆的有效长度，也就是要做下沉的区间范围
 * @return arr: 调整后的二叉堆数组
 */
function downAdjust(arr, parentIndex, length) {
  // const len = arr.length;
  // 保存父节点的值，用于最后赋值
  let temp = arr[parentIndex]
  // 左节点下标值
  let childIndex = parentIndex * 2 + 1;
  // 如果存在左孩子节点
  while(childIndex < length) {
    // 检测是否存在右节点，且右节点比左节点大点，则取右节点下标值；否则还是使用左节点下标
    if(childIndex + 1 < length && arr[childIndex + 1] > arr[childIndex]) {
      childIndex++;
    }
    // 如果父节点值比左右节点中最大的节点值都要大，那么结束
    if(temp > arr[childIndex]) break;
    // 否则，将爷节点与最大子节点值交换
    arr[parentIndex] = arr[childIndex]
    parentIndex = childIndex
    childIndex = parentIndex * 2 + 1
  }
  arr[parentIndex] = temp
  return arr;
}

const testArr2 = downAdjust([4,2,9,36,7,8,1,3], 0, 8)
console.log(testArr2); // [ 9, 2, 8, 36, 7, 4, 1, 3 ]


/**
 * @description 构造二叉堆，将无序的完全二叉树转换成一个二叉堆（最小堆）
 * @param arr: 待调整的完全二叉树数组
 * @return arr: 调整后的二叉堆
 */
function buildMaxHeap(arr) {
  let childIndex = arr.length - 1
  let parentInddex = getParentIndex(childIndex)
  for(let i = parentInddex; i >= 0; i--) {
    downAdjust(arr, i, arr.length)
  }
  return arr;
}
const testArr3 = buildMaxHeap([4,2,9,36,7,8,1,3])
console.log("testArr3:", testArr3); // [ 36, 7, 9, 3, 4, 8, 1, 2 ]

堆的下沉操就是把要下沉的元素（后面记做parent了），依次对比它的左右子节点，记录子节点中最大值 childMax = max(左子节点，右子节点)，如果子节点max都比parent小，则结束；如果childMax > parent，则两者交换位置。然后将这个parent继续做下沉操作，直至子节点中没有比parent大的值或没有子节点为止。

其实堆下沉，我们往往是用来用删除操作。
比如：这个最大堆[ 36, 7, 9, 3, 4, 8, 1, 2 ]，我们如果要删除36，就是把2和36的位置交换，然后删除36，然后对2进行下沉,最后得到[ 9, 7, 8, 3, 4, 2, 1 ]，会发现9是下个堆的最大值，也就是原堆的第二大值。

利用这个特性，我们每次将删除的堆顶，都不做删除操作（假删除操作），而是丢到除了有序区间的最后一位。我们就可以简单地实现堆排序了：

1. 初始堆[ 36, 7, 9, 3, 4, 8, 1, 2 ]，第1次执行删除36，最后一位与36交换得到[ 2, 7, 9, 3, 4, 8, 1, 36 ]，然后对2进行下沉操作时，忽略最后一个节点，这样就可以得到[ 9, 7, 8, 3, 4, 2, 1, 36 ],执行第1次后就可以把最大值放在最后了
2. 第2次执行删除9，和倒数第二位1换位置，[ 1, 7, 8, 3, 4, 2, 9, 36 ]，然后对1进行下沉操作，忽略后二位节点，这样就可以得到[ 8, 7, 2, 3, 4, 1, 9, 36 ]，执行第2次后就可以得到最后两位的有序区间了
3. 第3次执行删除8，和倒数第三位1交换位置[ 1, 7, 2, 3, 4, 8, 9, 36 ]，然后对1进行下沉操作，忽略后三位节点，这样就可以得到[ 7, 4, 2, 3, 1, 8, 9, 36 ]
4. 第4次执行删除7,和倒数第4位交换位置[ 1, 4, 2, 3, 7, 8, 9, 36 ]，然后对1进行下沉操作，忽略后4四位有序区间，这样就可以得到[ 4, 3, 2, 1, 7, 8, 9, 36 ]
5. 第5次执行删除4,和倒数第5位交换位置[ 1, 3, 2, 4, 7, 8, 9, 36 ]，然后对1进行下沉操作，忽略后5四位有序区间，这样就可以得到[ 3, 1, 2, 4, 7, 8, 9, 36 ]
6. 第6次执行删除3,和倒数第6位交换位置[ 2, 1, 3, 4, 7, 8, 9, 36 ]，然后对2进行下沉操作，忽略后6四位有序区间，这样就可以得到[ 1, 2, 3, 4, 7, 8, 9, 36 ]，这时就剩下1个1是堆顶了，没有要比较的队列了，因为右边的已经全是有序队列了，所以此时结束后，就能得到排序结果了

所以只要在最大堆的基础上，做次遍历删除操作就好了：

/*
*  堆排序实现
*/
function heapSort(arr) {
  // 将无序数组转换成为最大堆
  let heap = buildMaxHeap(arr)

  // 然后依次对堆进行删除操作
  for(let i = heap.length -1; i > 0; i--) {
    // 每次将堆顶假删除，放最后
    [ heap[0], heap[i] ] = [ heap[i], heap[0] ]
    // 然后对新的堆顶做下沉操作，构成新的最大堆
    downAdjust(heap, 0, i)
  }
  return heap;
}

let heap = heapSort([7, 36, 9, 3, 4, 8, 1, 2])
console.log('heap:', heap); // [ 1, 2, 3, 4, 7, 8, 9, 36 ]

这时候，我们来分析下它的时间复杂度和空间复杂度了：

• 空间复杂度，基本上没有创建新地址空间,所以是O(1)
• 时间复杂度：
  1. 把无序数组转换成堆的复杂度是O(n)
  2. 下沉操作是O(logn)，遍历操作是O(n)
     所以总的是O(n + nlogn),相当于O(n(1+logn)),然后常量可以忽略，所以平均下来就约等于O(nlogn)了

排序算法系列文章传送门(未完，持续更新中)：
排序算法-1（javascript） 冒泡、选择、插入、希尔排序的实现
排序算法-2（javascript） 快速排序的实现
排序算法-3（javascript） 堆排序的实现
排序算法-4（javascript） 归并排序的实现