堆（Heap）结构

核心特性

完全二叉树结构，分为大顶堆（父节点≥子节点）和小顶堆（父节点≤子节点）

核心操作：插入（O (log n)）、删除堆顶（O (log n)）、获取堆顶（O (1)）

适用场景：快速获取极值（如 Top K 问题、优先级队列）

代码实现（小顶堆）

class MinHeap {
  constructor() {
    this.heap = []; // 基于数组存储堆（索引0为堆顶）
  }

  // 获取父节点索引
  _getParentIndex(index) {
    return Math.floor((index - 1) / 2);
  }

  // 获取左子节点索引
  _getLeftChildIndex(index) {
    return index * 2 + 1;
  }

  // 获取右子节点索引
  _getRightChildIndex(index) {
    return index * 2 + 2;
  }

  // 交换两个节点的值
  _swap(i1, i2) {
    [this.heap[i1], this.heap[i2]] = [this.heap[i2], this.heap[i1]];
  }

  // 上浮（插入时，维护堆的性质）
  _bubbleUp(index) {
    if (index === 0) return; // 堆顶无需上浮
    const parentIndex = this._getParentIndex(index);
    // 小顶堆：子节点 < 父节点，交换
    if (this.heap[index] < this.heap[parentIndex]) {
      this._swap(index, parentIndex);
      this._bubbleUp(parentIndex); // 继续上浮父节点
    }
  }

  // 下沉（删除堆顶时，维护堆的性质）
  _bubbleDown(index) {
    const leftIndex = this._getLeftChildIndex(index);
    const rightIndex = this._getRightChildIndex(index);
    let smallestIndex = index;

    // 找到子节点中较小的那个
    if (leftIndex < this.heap.length && this.heap[leftIndex] < this.heap[smallestIndex]) {
      smallestIndex = leftIndex;
    }
    if (rightIndex < this.heap.length && this.heap[rightIndex] < this.heap[smallestIndex]) {
      smallestIndex = rightIndex;
    }

    // 如果子节点更小，交换并继续下沉
    if (smallestIndex !== index) {
      this._swap(index, smallestIndex);
      this._bubbleDown(smallestIndex);
    }
  }

  // 插入元素
  insert(value) {
    this.heap.push(value);
    this._bubbleUp(this.heap.length - 1); // 从最后一个元素开始上浮
  }

  // 删除并返回堆顶元素（最小值）
  extractMin() {
    if (this.heap.length === 0) return null;
    if (this.heap.length === 1) return this.heap.pop();

    const min = this.heap[0];
    this.heap[0] = this.heap.pop(); // 用最后一个元素替换堆顶
    this._bubbleDown(0); // 从堆顶开始下沉
    return min;
  }

  // 获取堆顶元素（最小值，不删除）
  getMin() {
    return this.heap.length > 0 ? this.heap[0] : null;
  }

  // 获取堆的大小
  size() {
    return this.heap.length;
  }
}

适用场景

优先级队列：const priorityQueue = new MinHeap()（存储异步任务，优先级高的任务先执行）

Top K 问题：获取数组中前 K 个最大元素（用小顶堆存储 K 个元素，遍历数组时，比堆顶大的元素替换堆顶，最后堆中元素即为 Top K）

数据流中位数：维护两个堆（大顶堆存储左半部分数据，小顶堆存储右半部分数据），中位数可通过两个堆顶计算

注意

堆的插入和删除操作都需要维护堆的性质（上浮 / 下沉），时间复杂度为 O (log n)

小顶堆适合获取最小值，大顶堆适合获取最大值，根据需求选择