js实现堆

堆的基本概念

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

最大堆实现

以下是用JavaScript实现最大堆的完整代码示例：

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]];
  }

  insert(value) {
    this.heap.push(value);
    this.heapifyUp();
  }

  heapifyUp() {
    let index = this.heap.length - 1;
    while (index > 0) {
      const parentIndex = this.getParentIndex(index);
      if (this.heap[parentIndex] >= this.heap[index]) break;
      this.swap(parentIndex, index);
      index = parentIndex;
    }
  }

  extractMax() {
    if (this.heap.length === 0) return null;
    const max = this.heap[0];
    const last = this.heap.pop();
    if (this.heap.length > 0) {
      this.heap[0] = last;
      this.heapifyDown();
    }
    return max;
  }

  heapifyDown() {
    let index = 0;
    const length = this.heap.length;
    while (true) {
      const leftChildIndex = this.getLeftChildIndex(index);
      const rightChildIndex = this.getRightChildIndex(index);
      let largestIndex = index;

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

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

      if (largestIndex === index) break;
      this.swap(index, largestIndex);
      index = largestIndex;
    }
  }

  peek() {
    return this.heap.length > 0 ? this.heap[0] : null;
  }

  size() {
    return this.heap.length;
  }
}

最小堆实现

最小堆的实现与最大堆类似，只需调整比较逻辑：

class MinHeap {
  // 构造函数和方法与MaxHeap相同

  heapifyUp() {
    let index = this.heap.length - 1;
    while (index > 0) {
      const parentIndex = this.getParentIndex(index);
      if (this.heap[parentIndex] <= this.heap[index]) break;
      this.swap(parentIndex, index);
      index = parentIndex;
    }
  }

  heapifyDown() {
    let index = 0;
    const length = this.heap.length;
    while (true) {
      const leftChildIndex = this.getLeftChildIndex(index);
      const rightChildIndex = this.getRightChildIndex(index);
      let smallestIndex = index;

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

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

      if (smallestIndex === index) break;
      this.swap(index, smallestIndex);
      index = smallestIndex;
    }
  }

  extractMin() {
    // 同extractMax
  }
}

堆的应用示例

堆排序算法的实现：

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

  // 构建堆
  arr.forEach(num => heap.insert(num));

  // 依次提取最大值
  while (heap.size() > 0) {
    sorted.unshift(heap.extractMax());
  }

  return sorted;
}

// 使用示例
const unsorted = [3, 1, 4, 1, 5, 9, 2, 6];
const sorted = heapSort(unsorted);
console.log(sorted); // [1, 1, 2, 3, 4, 5, 6, 9]

性能分析

堆的插入和删除操作时间复杂度均为O(log n)，构建堆的时间复杂度为O(n)，堆排序的时间复杂度为O(n log n)。空间复杂度为O(1)（原地排序）或O(n)（非原地实现）。