最大堆的实现

定义

堆中某个节点（除去根节点）的值总是不大于其父节点的堆

优势

相较于优先队列，堆这种数据结构可以在入队和出队时，时间复杂度都稳定在O(lgn)级别

应用场景

如React的任务调度，优先级高的任务先执行

实现思路

使用数组来存储二叉堆，索引从1开始，对于一个节点，索引为i，其左孩子节点left索引为 2 * i, 右孩子节点right索引为2 * i + 1, 父亲节点索引为Math.floor(i / 2)。

常见操作

• heapify: 将一个无序数组建立成堆的过程，时间复杂度O(n)
• insert: 将一个元素插入到堆中，并保持堆的结构，时间复杂度O(lgn)
• pop: 取出堆中最大的元素，并保持剩余元素依旧维持堆结构，时间复杂度O(lgn)
• heapsort: 使用堆对数组进行排序，时间复杂度O(nlgn)
• shiftUp: 一个节点比父节点大，那么需要将它同父节点交换位置
• shiftDown: 一个节点比它的子节点小，那么需要将它向下移动

代码实现

class Heap {
  constructor(arr = [], sortBy = 0) {
    this.Heap = [];
    this.sortBy = sortBy;
    for (let i = 0; i < arr.length; i++) {
      this.Heap[i + 1] = arr[i];
    }
    for (let i = Math.floor(this.Heap.length / 2); i >= 1; i--) {
      // 从尾部一直往下移动数据到正确的位置
      this.shiftDown(i);
    }
  }

  shiftDown(index) {
    while (2 * index < this.Heap.length) {
      // 与子节点交换
      let i = 2 * index;
      if (i + 1 < this.Heap.length && this.compare(i + 1, i)) {
        // 与两个子节点中更小的交换位置
        i += 1;
      }
      // 已经移到了正确位置
      if (this.compare(index, i)) {
        break;
      }
      this.swap(index, i);
      index = i; // 子节点继续向下交换
    }
  }

  shiftUp(index) {
    while (index > 1 && this.compare(index, Math.floor(index / 2))) {
      this.swap(Math.floor(index / 2), index);
      index = Math.floor(index / 2);
    }
  }

  compare(i, j) {
    return this.sortBy === 0
      ? this.Heap[i] > this.Heap[j] // 最大堆
      : this.Heap[i] < this.Heap[j]; // 最小堆
  }

  insert(num) {
    this.Heap.push(num);
    this.shiftUp(this.getLenth());
  }

  pop() {
    let item;
    // 把最尾巴的提到最上 做shiftDown操作
    item = this.Heap[1];
    this.swap(1, this.getLenth());
    this.Heap.pop(); // 去掉尾节点
    this.shiftDown(1);
    return item;
  }

  getLenth() {
    return this.Heap.length - 1;
  }

  swap(i, j) {
    if (i !== j) {
      const temp = this.Heap[i];
      this.Heap[i] = this.Heap[j];
      this.Heap[j] = temp;
    }
  }
}

const maxHeap = new Heap([1, 2, 34, 52, 123, 4551]);
maxHeap.insert(2222);
console.log(maxHeap.pop(), maxHeap.pop());

const minHeap = new Heap([1, 2, 34, 52, 123, 4551], 1);
console.log(minHeap);
minHeap.insert(2222);
console.log(minHeap);

console.log(minHeap.pop(), minHeap.pop());