堆排序

class HeapSort {
  //建堆
  buildHeap(array) {
    //下标为0的位置保留
    const arr = [0].concat(array);

    for (let i = arr.length; i > 0; i--) {
      this._heapify(arr, arr.length, i);
    }
    return arr;
  }

  // 排序
  sort(array) {
    const arr = this.buildHeap(array); // 先建堆
    let len = arr.length - 1;
    while (len > 1) {
      this._swap(arr, 1, len); // 交换顶元素和最后一位。顶元素永远是最大的。
      len--;
      this._heapify(arr, len, 1); //剩下的元素重新建堆 直到len === 1 停止
    }
    return arr.slice(1);
  }

  // 堆化（构建大顶堆）
  _heapify(arr, len, i) {
    while (true) {
      let maxPos = i;
      // 如果index i拥有叶左节点 并且左节点较大
      if (i * 2 <= len && arr[i] < arr[i * 2]) {
        maxPos = i * 2;
      }
      // 如果index i拥有叶右节点 与Max节点比较大小，选出父/左/右中最大的一个
      if (i * 2 + 1 <= len && arr[maxPos] < arr[i * 2 + 1]) {
        maxPos = i * 2 + 1;
      }
      if (maxPos === i) break; // 循环直到i节点为最大值
      this._swap(arr, i, maxPos); // 交换位置, 父节点为父/左/右中最大的一个
      i = maxPos; // i为左/右节点，并尝试向下查找更大的值
    }
  }

  // 交换两个元素
  _swap(arr, i, j) {
    let temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }
}

var heapSort = new HeapSort();
heapSort.sort([1,2,3,2,3,5,1]); //[1, 1, 2, 2, 3, 3, 5]