## 堆排

### 基本知识

堆排序利用了二叉堆的特性来做，二叉堆通常用数组表示，并且二叉堆是一颗完全二叉树（所有叶节点（最底层的节点）都是从左往右顺序排序，并且其他层的节点都是满的）。二叉堆又分为大根堆与小根堆。

- 大根堆是某个节点的所有子节点的值都比他小

- 小根堆是某个节点的所有子节点的值都比他大

堆排序的原理就是组成一个`大根堆`或者`小根堆`。以小根堆为例，某个节点的左边子节点索引是 `i * 2 + 1`，右边是 `i * 2 + 2`，父节点是 `(i - 1) /2`。

- 首先遍历数组，判断该节点的父节点是否比他小，如果小就交换位置并继续判断，直到他的父节点比他大

- 重新以上操作 1，直到数组首位是最大值

- 然后将首位和末尾交换位置并将数组长度减一，表示数组末尾已是最大值，不需要再比较大小

- 对比左右节点哪个大，然后记住大的节点的索引并且和父节点对比大小，如果子节点大就交换位置
- 重复以上操作 3 - 4 直到整个数组都是大根堆。

```javascript
           大根堆                                小根堆

             50                                   10
           /    \                               /    \
         45      40                           20     15
        /  \     / \                         /  \   /  \
      20   25   35  30                     25   50 30   40
     /  \                                 /  \
    10   15                             35   45
```

假设，此时我们对大根堆中的结点按层进行编号，将这种逻辑结构映射到数组中就是下面这个样子

**arr = [50, 45, 40, 20, 25, 35, 30, 10, 15]**

该数组从逻辑上讲就是一个堆结构，我们用简单的公式来描述一下堆的定义就是：

```javascript
大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2] // a[0] >= a[1] && a[0] >= a[2]

小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2] // a[0] <= a[1] && a[0] <= a[2]
```

### 算法思想

将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余 n-1 个元素重新构造成一个堆，这样会得到 n 个元素的次小值。如此反复执行，便能得到一个有序序列了

- 构造初始堆。将给定无序序列构造成一个大顶堆（一般升序采用大顶堆，降序采用小顶堆)。

- 将堆顶元素与末尾元素进行交换，使得末尾元素最大(也就是数组 `arr[arr.length-1]` 为最大)，然后继续调整堆，再讲堆顶元素与末尾元素交换，得到第二大元素(也就是数组 `arr[arr.length-2]` 为第二大)，反复交换

### 代码

```javascript
/**
 * @desc 构建大根堆
 */
function heapSort(arr) {
  // 构建大根堆
  for (let i = parseInt(arr.length / 2) - 1; i >= 0; i--) {
    //从第一个非叶子结点从下至上，从右至左调整结构
    ajustHeap(arr, i, arr.length);
  }

  // 经过上面的 for 循环之后，构建的是一个将 无序数组 arr 构建成了一个大根堆
  console.log(arr); // [ 10, 9, 7, 8, 3, 2, 4, 6, 5, 1 ]

  // 调整堆结构 + 交换堆顶元素与末尾元素
  for (let j = arr.length - 1; j > 0; j--) {
    // swap(arr, 0, j) // 堆顶元素和末尾元素交换
    let temp = arr[0];
    arr[0] = arr[j];
    arr[j] = temp;
    ajustHeap(arr, 0, j); // 重新对堆进行调整
  }

  return arr; // [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
}

/**
 * @desc 调整大顶堆（仅是调整过程，建立在大顶堆已构建的基础上）
 */
function ajustHeap(arr, i, length) {
  let temp = arr[i]; // 取出当前的元素
  for (let k = i * 2 + 1; k < length; k = k * 2 + 1) {
    //从i结点的左子结点开始，也就是2i+1处开始
    if (k + 1 < length && arr[k] < arr[k + 1]) {
      //如果左子结点小于右子结点，k指向右子结点
      k++;
    }
    if (arr[k] > temp) {
      arr[i] = arr[k];
      i = k;
    } else {
      break;
    }
  }
  arr[i] = temp; // 把temp放在最终的位置
}

var arr = [9, 6, 2, 5, 3, 7, 4, 8, 10, 1];
console.log(heapSort(arr)); // [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
```

### 时间复杂度和空间复杂度

时间复杂度为: O(logN)，空间复杂度为: O(1)