js实现堆

堆的基本概念

堆是一种特殊的完全二叉树，分为最大堆和最小堆。最大堆的每个父节点值大于或等于子节点值，最小堆的每个父节点值小于或等于子节点值。堆常用于优先队列、堆排序等场景。

堆的数组表示

堆通常用数组表示，对于索引i的节点：

• 父节点索引：Math.floor((i - 1) / 2)
• 左子节点索引：2 * i + 1
• 右子节点索引：2 * i + 2

最小堆实现代码

class MinHeap {
  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]];
  }

  // 上移操作
  shiftUp(index) {
    if (index === 0) return;
    const parentIndex = this.getParentIndex(index);
    if (this.heap[parentIndex] > this.heap[index]) {
      this.swap(parentIndex, index);
      this.shiftUp(parentIndex);
    }
  }

  // 下移操作
  shiftDown(index) {
    const leftChildIndex = this.getLeftChildIndex(index);
    const rightChildIndex = this.getRightChildIndex(index);
    let minIndex = index;

    if (leftChildIndex < this.heap.length && this.heap[leftChildIndex] < this.heap[minIndex]) {
      minIndex = leftChildIndex;
    }

    if (rightChildIndex < this.heap.length && this.heap[rightChildIndex] < this.heap[minIndex]) {
      minIndex = rightChildIndex;
    }

    if (minIndex !== index) {
      this.swap(index, minIndex);
      this.shiftDown(minIndex);
    }
  }

  // 插入元素
  insert(value) {
    this.heap.push(value);
    this.shiftUp(this.heap.length - 1);
  }

  // 删除堆顶元素
  pop() {
    if (this.heap.length === 0) return null;
    const top = this.heap[0];
    const last = this.heap.pop();
    if (this.heap.length > 0) {
      this.heap[0] = last;
      this.shiftDown(0);
    }
    return top;
  }

  // 获取堆顶元素
  peek() {
    return this.heap.length > 0 ? this.heap[0] : null;
  }

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

最大堆实现代码

将最小堆的比较符号反转即可实现最大堆：

class MaxHeap {
  // ... (其他方法与MinHeap相同)

  shiftUp(index) {
    if (index === 0) return;
    const parentIndex = this.getParentIndex(index);
    if (this.heap[parentIndex] < this.heap[index]) {  // 改为小于
      this.swap(parentIndex, index);
      this.shiftUp(parentIndex);
    }
  }

  shiftDown(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.shiftDown(maxIndex);
    }
  }
}

堆的应用示例

// 创建最小堆
const minHeap = new MinHeap();
minHeap.insert(3);
minHeap.insert(2);
minHeap.insert(1);
console.log(minHeap.pop()); // 输出1

// 创建最大堆
const maxHeap = new MaxHeap();
maxHeap.insert(1);
maxHeap.insert(2);
maxHeap.insert(3);
console.log(maxHeap.pop()); // 输出3

堆排序实现

利用堆可以实现堆排序算法：

function heapSort(arr) {
  const heap = new MinHeap();
  const sorted = [];

  // 构建堆
  for (let num of arr) {
    heap.insert(num);
  }

  // 依次取出堆顶元素
  while (heap.size() > 0) {
    sorted.push(heap.pop());
  }

  return sorted;
}

console.log(heapSort([3, 1, 4, 1, 5, 9, 2, 6])); // [1, 1, 2, 3, 4, 5, 6, 9]