堆排序

参考：堆排序中建堆过程时间复杂度O(n)怎么来的？

二叉树-js(1.基础知识与基本操作)：中介绍了数组如何转成二叉树

[1,2,2,3,4,4,3]

转为二叉树的结构为：

    1
   / \
  2   2
 / \ / \
3  4 4  3

利用了父子节点之间的数据关系

父节点在数组中的下标为n，左子节点为n*2+1,右子节点为n*2+2

子节点在数组中下标为v，父节点就为Math.floor((v-1)/2)

下面首先介绍如何在不将数组转换为树结构的情况下进行前序遍历:

function preorderShow (arr, index = 0, result = []) {
  if (index >= arr.length) { return result }
  result.push(arr[index])
  preorderShow(arr, index * 2 + 1, result)
  return preorderShow(arr, index * 2 + 2, result)
}
let result = preorderShow([0, 1, 2, 3, 4, 5, 6])
console.log(result) // [ 0, 1, 3, 4, 2, 5, 6 ]

堆排序原理：

​ 1.大顶堆的概念： 每个子树的根节点的值都比它的子树大

​ 2.原理：类似选择、冒泡排序，都是在一次遍历中找出一个最大值，然后多次进行这个操作。每当将树结构整理成大顶堆时，都能得到一个最大值，剔除这个最大值之后对剩下的树结构再次整理，得到第二大值。

​ 3.整理出大顶堆步骤的图解：

以下为一个待处理的二叉树 [6,2,14,7,8,3,5]

从最后一层开始，3个一组进行排序，将最大值交换到父节点

再同样的交换顺序保证上一层的父节点也是最大值

但是交换之后发现子树的大顶堆结构被破坏了，所以再次对子树进行交换

从倒数第二层开始，一旦进行交换就有可能破坏子树的大顶堆结构，再对子树进行交换处理，中间又可能影响子树的子树，所以这是一个递归的处理过程。

从最后一层开始，将每3个一组中的父节点交换为最大值，这个为遍历过程，交换过程会影响子树的大顶堆结构，对子树的大顶堆结构的纠正是一个递归的过程。

第一次构建大顶堆的分步代码如下：

1. 3个节点一组，将最大的放到根节点，再对子树进行纠正

function swap (arr, i, j) {
  let temp = arr[i]
  arr[i] = arr[j]
  arr[j] = temp
}

function maxHeap (arr, index) { // 父节点、左节点、右节点中将最大值放在父节点； 对因此收到影响的子树纠正为大顶堆
  let left = index * 2 + 1
  let right = index * 2 + 2
  let max = index

  if (left < arr.length && arr[left] > arr[max]) {
    max = left
  }

  if (right < arr.length && arr[right] > arr[max]) {
    max = right
  }
  if (index !== max) { // 根节点不为最大值
    swap(arr, max, index)
    maxHeap(arr, max) // 修正因交换产生问题的子树
  }
}
function swap (arr, i, j) {
  let temp = arr[i]
  arr[i] = arr[j]
  arr[j] = temp
}

2.从最后一组3个节点开始，从下往上构建一个大顶堆

function firstMaxHeap (arr) {
  let first = Math.floor((arr.length - 2) / 2) // 最后一个元素为下标为arr.length -1 ,通过根节点下标为 Math.floor((i-1)/2) 找出第一个要遍历的根节点
  for (let i = first; i >= 0; i--) {
    maxHeap(arr, i)
  }
}
let arr = [6,13,18,8,7,22,2]
firstMaxHeap(arr) 
console.log(arr) // [22,13,18,8,7,6,2]

输入[6,13,18,8,7,22,2]构建大根堆后结果为[22,13,18,8,7,6,2] 。图示如下

疑问: ????堆排序是一个由下向上的过程，即使不纠正子树为大顶堆仍旧可以将已遍历的节点中最大的值向上传递，为什么还要对子树的大顶堆结构进行纠正?

解答：首先看堆排序的时间复杂度是优于冒泡与选择排序的，而等于快速排序。也就是说堆排序也运用了二分的思想。

排序方法	平均时间
冒泡排序	O(n^2)
选择排序	O(n^2)
快速排序	O(nlogn)
堆排序	O(nlogn)

由于堆排序从上到下构建，第一次找出最大值时构建好了如下大顶堆

[22,13,18,8,7,6,2]

找出第二大值之前需要将22从树中除去，再次进行构建大顶堆的

不破坏树结构除去根节点22的方法：将根节点与一个叶子节点交换位置，再删除这个叶子节点

当选择最后一个叶子节点2与22交换位置之后，此时的数组结构为[2,13,18,8,7,6,22]

22如升序冒泡排序的第一轮排序一样放置在了数组的末尾，下一次对arr.slice(0,arr.length - 1)进行排序

此时又完成了一次大顶堆的构建，并且13所在的子树完全没有被遍历到，只遍历了根节点的右子树。由于第一次构建大顶堆的过程中就维护所有子树都是大顶堆，所以13一定是根节点的左子树中的最大值，18>13完全不用再考虑13这颗子树。

否则如果13不是大顶堆的话，又要重复从底端最后一层开始向上构建大顶堆，那么堆排序的时间复杂度不是O（nlogn）而是O（n^2）。

第一次构建好大顶堆之后，根节点与最后一个叶子节点交换位置，再从树中被排除,余下的节点再此构建大顶堆

代码如下：

function swap (arr, i, j) {
  let temp = arr[i]
  arr[i] = arr[j]
  arr[j] = temp
}

function maxHeap (arr, size, index) { // 父节点、左节点、右节点中将最大值放在父节点； 对因此受到影响的子树纠正为大顶堆
  let left = index * 2 + 1
  let right = index * 2 + 2
  let max = index

  if (left < size && arr[left] > arr[max]) { // arr中size之后的节点都是之前构建大顶堆时选出来的最大值
    max = left
  }

  if (right < size && arr[right] > arr[max]) { // arr中size之后的节点都是之前构建大顶堆时选出来的最大值
    max = right
  }
  if (index !== max) { // 根节点不为最大值
    swap(arr, max, index)
    maxHeap(arr, max) // 修正因交换产生问题的子树
  }
}

function heapSort (arr) {
  // 第一次构建大顶堆
  let first = Math.floor((arr.length - 2) / 2) // 最后一个元素为下标为arr.length -1 ,通过根节点下标为 Math.floor((i-1)/2) 找出第一个要遍历的根节点
  for (let i = first; i >= 0; i--) {
    maxHeap(arr, arr.length, i)
  }

  // 第二次及以后构建大顶堆
  for (let i = arr.length - 1; i > 0; i--) {
    // 交换根节点与最后一个叶子节点
    swap(arr, 0, i)

    // 排除之前选出来的最大值后对剩下的数组再次建立大顶堆选出最大值
    maxHeap(arr, i, 0)
  }
}

let arr = [6, 13, 18, 8, 7, 22, 2]
heapSort(arr)
console.log(arr) // [ 2, 6, 8, 7, 18, 13, 22 ]