堆排序(Heap Sort)

提示

数据结构——堆 堆：实际上可以理解为是一个完全二叉树的数组对象。

最大堆：堆中的某个节点的值必须不大于其父节点的值，堆总是一颗完全二叉树。

最小堆：堆中的某个节点的值必须不小于其父节点的值，堆总是一颗完全二叉树。

普通队列：先进先出，后进后出。（本质就是由时间的顺序决定出队顺序）。

优先队列：出队顺序和入队顺序无关，和优先级有关。处理【动态】任务。

实现优先队列最好的方式是是用堆这种数据结构。

class MaxHeap {
  // constructor(capacity) {
  //   this.data = new Array(capacity + 1);
  //   this.count = 0;
  // }
  constructor(arr, length) {
    this.data = new Array(length + 1);
    for (let i = 0; i < arr.length; i++) {
      this.data[i + 1] = arr[i];
    }
    this.count = length;
    for (let k = Math.floor(this.count / 2); k >= 1; k--) {
      this.shiftDown(k);
    }
  }
  getSize() {
    return this.count;
  }
  isEmpty() {
    return this.count === 0;
  }
  insert(value) {
    this.data[this.count + 1] = value;
    this.count++;
    this.shiftUp(this.count);
  }
  extractMax() {
    if (this.count <= 0) return;
    const ret = this.data[1];
    this.swap(this.data, 1, this.count);
    this.count--;
    this.shiftDown(1);
    return ret;
  }
  shiftUp(k) {
    while (k >= 1 && this.data[k] > this.data[Math.floor(k / 2)]) {
      this.swap(this.data, k, Math.floor(k / 2));
      k = Math.floor(k / 2);
    }
  }
  shiftDown(k) {
    //判断有左孩子
    while (2 * k <= this.count) {
      let j = 2 * k;
      if (j + 1 <= this.count && this.data[j] < this.data[j + 1]) {
        //判断是否有右孩子并且值大
        j += 1;
      }
      if (this.data[k] >= this.data[j]) break;
      this.swap(this.data, k, j);
      k = j;
    }
  }
  swap(arr, index1, index2) {
    [arr[index1], arr[index2]] = [arr[index2], arr[index1]];
  }
}
function heapSort(arr) {
  // const maxHeap = new MaxHeap(arr.length + 1);
  // for (let i = 0; i < arr.length; i++) {
  //   maxHeap.insert(arr[i]);
  // }
  // for (let i = arr.length; i > 0; i--) {
  //   const v = maxHeap.extractMax();
  //   arr[i - 1] = v;
  // }
  // return arr;
  const maxHeap = new MaxHeap(arr, arr.length);

  for (let i = arr.length; i > 0; i--) {
    const v = maxHeap.extractMax();
    arr[i - 1] = v;
  }
  return arr;
}