堆排序

最大堆

// 最大堆
class Maxheap {
  constructor() {
    // 堆索引从1开始，第0个元素位置不使用
    this.arr = [null];
  }
  // 返回堆大小
  size() {
    return this.arr.length - 1;
  }
  // 添加元素
  insert(item) {
    this.arr.push(item);
    // 添加完成后执行shiftUp，将元素移动到合适的位置，使得堆满足最大堆
    this.__shiftUp(this.arr.length - 1);
  }
  __shiftUp(k) {
    // 循环遍历新加入元素的父节点，比父节点大则与父节点交换位置
    while (k > 1 && this.arr[Math.floor(k / 2)] < this.arr[k]) {
      let mid = this.arr[Math.floor(k / 2)];
      this.arr[Math.floor(k / 2)] = this.arr[k];
      this.arr[k] = mid;
      // 逐级查找父节点进行对比
      k = Math.floor(k / 2);
    }
  }
  // 取出优先级最大的元素，即取出最大堆顶级元素
  extractMax() {
    let max = this.arr[1];
    // 取出第一个元素后将堆最后一个元素移到第一位
    this.arr[1] = this.arr[this.size()];
    this.arr.pop();
    // 对从最后一位移过来的元素执行shiftDown，将元素移动到合适的位置，使得堆满足最大堆
    this.__shiftDown(1);
    return max;
  }
  __shiftDown(k) {
    // 循环遍历k元素的子节点，将其与两个子节点中较大的节点交换位置
    while (2 * k <= this.size()) {
      let j = 2 * k;
      // 当第二个子元素存在且比第一个子元素大时，直接与第二个子元素进行对比
      if (j + 1 <= this.size() && this.arr[j + 1] > this.arr[j]) {
        j++;
      }
      // 对比k元素和子元素中较大一方的大小，子元素更大则交换
      if (this.arr[j] > this.arr[k]) {
        let mid = this.arr[k];
        this.arr[k] = this.arr[j];
        this.arr[j] = mid;
      }
      // 进行一下层子元素对比
      k = j;
    }
  }
}

// 堆排序
function heapSort(arr) {
  const heap = new Maxheap();
  // 将元素都插入到堆中
  for (let i = 0; i < arr.length; i++) {
    heap.insert(arr[i]);
  }
  // 遍历取出堆的最大值倒叙存入数组，使得数组从小到大排序
  for (let i = arr.length - 1; i >= 0; i--) {
    arr[i] = heap.extractMax();
  }
  return arr;
}

// 优化堆排序
function heapSortBetter(arr) {
  const heapBetter = new Maxheap();
  // 直接将数组整体存入
  heapBetter.arr = heapBetter.arr.concat(arr);
  // Math.floor(heapBetter.size() / 2)是第一个非叶子节点的索引，也就是最后一个有子元素的节点。
  // 从这个节点向前遍历进行shiftDown，将整个堆转为最大堆
  for (let i = Math.floor(heapBetter.size() / 2); i >= 1; i--) {
    heapBetter.__shiftDown(i);
  }
  for (let i = arr.length - 1; i >= 0; i--) {
    arr[i] = heapBetter.extractMax();
  }
  return arr;
}

// 原地堆排序
// 原地堆排序是在原数组上面进行排序，不利用额外的储存空间，所以索引是从0开始
// i元素的父节点索引为Math.floor((i - 1) / 2) 
// i元素的左侧子节点元素索引为 2 * i + 1，右侧子节点元素索引为 2 * i + 2
// 第一个非叶子节点元素的索引为 (length - 1 - 1) / 2
function heapSortSelf(arr) {
  let length = arr.length
  // 处理数组，将数组转为最大堆
  for (let i = Math.floor((length - 1 - 1) / 2); i >= 0; i--) {
    __shiftDown(arr, length, i)
  }
  // 对处理好的最大堆元素进行排序，将最大值和数组末尾交换，再将剩下的部分继续转为最大堆
  for (let j = length - 1; j > 0; j--) {
    let mid = arr[0]
    arr[0] = arr[j]
    arr[j] = mid
    // 每次需要转为最大堆的部分都在减小，因为数组的后面排好序的部分在增加
    __shiftDown(arr, j, 0)
  }
  // 将第i个元素移动到合适的位置，使得数组中[0, length]的部分成为最大堆
  function __shiftDown(arr, length, i) {
    while (2 * i + 1 < length) {
      let j = 2 * i + 1
      if (j + 1 < length && arr[j + 1] > arr[j]) {
        j++
      }
      if (arr[i] < arr[j]) {
        let mid = arr[j]
        arr[j] = arr[i]
        arr[i] = mid
      }
      i = j
    }
  }
  return arr
}

索引堆