堆

堆的定义

堆是一种特殊的完全二叉树，其满足以下性质：

• 任意节点的值总是大于等于（大顶堆）或小于等于（小顶堆）子节点的值
• 堆总是一棵完全二叉树
• 堆中任意节点的值都遵循堆序性

堆的实现

最小堆实现

class MinHeap {
  constructor() {
    this.heap = [];
  }

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

  // 插入节点
  insert(val) {
    this.heap.push(val);
    this.heapifyUp(this.heap.length - 1);
  }

  // 向上调整
  heapifyUp(index) {
    while (index > 0) {
      const parentIndex = this.getParentIndex(index);
      if (this.heap[parentIndex] <= this.heap[index]) break;
      [this.heap[parentIndex], this.heap[index]] = [this.heap[index], this.heap[parentIndex]];
      index = parentIndex;
    }
  }

  // 提取最小值
  extractMin() {
    if (this.heap.length === 0) return null;
    const min = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.heapifyDown(0);
    return min;
  }

  // 向下调整
  heapifyDown(index) {
    const leftChild = 2 * index + 1;
    const rightChild = 2 * index + 2;
    let smallest = index;

    if (leftChild < this.heap.length && this.heap[leftChild] < this.heap[smallest]) {
      smallest = leftChild;
    }
    if (rightChild < this.heap.length && this.heap[rightChild] < this.heap[smallest]) {
      smallest = rightChild;
    }
    if (smallest !== index) {
      [this.heap[index], this.heap[smallest]] = [this.heap[smallest], this.heap[index]];
      this.heapifyDown(smallest);
    }
  }
}

堆的操作复杂度

操作	时间复杂度
插入元素	O(log n)
删除元素	O(log n)
获取极值	O(1)
堆排序	O(n log n)