带你读《图解算法小抄》八、堆（2）

class MaxHeap {
  constructor() {
    this.heap = [];
  }
  // 获取父节点的索引
  getParentIndex(index) {
    return Math.floor((index - 1) / 2);
  }
  // 获取左子节点的索引
  getLeftChildIndex(index) {
    return 2 * index + 1;
  }
  // 获取右子节点的索引
  getRightChildIndex(index) {
    return 2 * index + 2;
  }
  // 交换元素位置
  swap(index1, index2) {
    [this.heap[index1], this.heap[index2]] = [this.heap[index2], this.heap[index1]];
  }
  // 上移操作（向上调整堆）
  siftUp(index) {
    if (index === 0) {
      return;
    }
    const parentIndex = this.getParentIndex(index);
    if (this.heap[parentIndex] < this.heap[index]) {
      this.swap(parentIndex, index);
      this.siftUp(parentIndex);
    }
  }
  // 下移操作（向下调整堆）
  siftDown(index) {
    const leftChildIndex = this.getLeftChildIndex(index);
    const rightChildIndex = this.getRightChildIndex(index);
    let maxIndex = index;
    if (leftChildIndex < this.heap.length && this.heap[leftChildIndex] > this.heap[maxIndex]) {
      maxIndex = leftChildIndex;
    }
    if (rightChildIndex < this.heap.length && this.heap[rightChildIndex] > this.heap[maxIndex]) {
      maxIndex = rightChildIndex;
    }
    if (maxIndex !== index) {
      this.swap(index, maxIndex);
      this.siftDown(maxIndex);
    }
  }
  // 插入元素到堆中
  insert(value) {
    this.heap.push(value);
    this.siftUp(this.heap.length - 1);
  }
// 获取堆顶元素（最大值）
  peek() {
    if (this.heap.length === 0) {
      return null;
    }
    return this.heap[0];
  }
  // 删除堆顶元素（最大值）
  remove() {
    if (this.heap.length === 0) {
      return null;
    }
    const maxValue = this.heap[0];
    const lastValue = this.heap.pop();
    if (this.heap.length > 0) {
      this.heap[0] = lastValue;
      this.siftDown(0);
    }
    return maxValue;
  }
  // 获取堆的大小
  size() {
    return this.heap.length;
  }}