之前学到二叉堆的时候，发现可以利用二叉堆来做排序算法。其基本原理就是利用其堆顶元素为数组的最大值或者最小值的特性，截取堆顶元素后再重新调整为最大或最小堆，最后按顺序截取的堆顶元素就是一个升序序列或将序序列。

堆化算法

移除堆顶元素，将堆的最后一个元素移动到堆顶，从堆顶开始调整堆，直到合适的位置。

算法思路

1. 构建一个最大堆，堆顶元素为最大值;
2. 交换堆顶元素和堆的最后一个元素，标记最后的元素为堆化截止点；
3. 调整堆为最大堆，直到堆化截止点；
4. 交换堆顶元素和上次的堆化截止点，重新调整截止点；
5. 重复 2-3 步骤；
6. 直到截止点为 1；

堆类型选择

• 升序排序 => 最大堆
• 降序陪序 => 最小堆

代码实现

// 升序排序 - 最大堆
class MaxHeap {
  constructor() {
    this.heap = [];
  }

  insert(val) {
    const { heap } = this;
    heap.push(val);
    if (heap.length > 1) {
      this._siftUp(heap.length - 1);
    }
  }

  _siftUp(index) {
    const { heap } = this;
    const parent = this.parent(index);
    if (parent === undefined) return;
    if (heap[parent] < heap[index]) {
      [heap[parent], heap[index]] = [heap[index], heap[parent]];
      this._siftUp(parent);
    }
  }

  sort() {
    const { heap } = this;
    let length = heap.length - 1;
    while (length > 0) {
      [heap[0], heap[length]] = [heap[length], heap[0]];
      this._siftDown(0, length);
      length--;
    }
  }

  _siftDown(index, last) {
    const { heap } = this;
    let current = index;
    const left = this.leftChild(current);
    const right = this.rightChild(current);
    if (left >= last || right >= last) return;
    if (heap[current] < heap[left]) {
      current = left;
    }
    if (heap[current] < heap[right]) {
      current = right;
    }

    if (current !== index) {
      [heap[current], heap[index]] = [heap[index], heap[current]];
      this._siftDown(current, last);
    }
  }

  leftChild(index) {
    return 2 * index + 1;
  }

  rightChild(index) {
    return 2 * index + 2;
  }
  parent(index) {
    if (index === 0) {
      return undefined;
    }
    return Math.floor((index - 1) / 2);
  }

  display() {
    console.log(this.heap);
  }
}

const maxHeap = new MaxHeap();

maxHeap.insert(1);
maxHeap.insert(5);
maxHeap.insert(4);

maxHeap.insert(3);
maxHeap.insert(2);
maxHeap.insert(6);

maxHeap.display();

maxHeap.sort();

maxHeap.display();

应用场景

• 可以用来实现优先队列，比如 React 的 Scheduler 的实现

算法分析

这是一个不稳定算法，因为相同值的元素不能确保排序后位置不变

Code Pen

Code Pen