在Javascript中实现递归maxHeap

在JavaScript中实现一个递归的最大堆（maxHeap）是一种常见的数据结构操作，它允许我们高效地获取和调整堆中的最大元素。最大堆是一种特殊的完全二叉树，其中每个父节点的值都大于或等于其子节点的值。

基础概念

堆（Heap）：一种特殊的树形数据结构，满足堆属性，可以是最大堆或最小堆。
最大堆（Max Heap）：每个父节点的值都大于或等于其子节点的值。

实现优势

高效的插入和删除最大元素：时间复杂度为O(log n)。
快速访问最大元素：时间复杂度为O(1)。

类型

数组实现：通常使用数组来实现堆，利用索引关系快速访问父节点和子节点。

应用场景

优先队列：用于实现任务调度、事件处理等。
排序算法：如堆排序。

实现示例

以下是一个简单的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.bubbleUp(this.heap.length - 1);
  }

  // 上浮操作
  bubbleUp(index) {
    while (index > 0 && this.heap[index] > this.heap[this.getParentIndex(index)]) {
      this.swap(index, this.getParentIndex(index));
      index = this.getParentIndex(index);
    }
  }

  // 提取最大元素
  extractMax() {
    if (this.heap.length === 1) return this.heap.pop();
    const max = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.bubbleDown(0);
    return max;
  }

  // 下沉操作
  bubbleDown(index) {
    let largestIndex = index;
    const leftChildIndex = this.getLeftChildIndex(index);
    const rightChildIndex = this.getRightChildIndex(index);

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

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

    if (largestIndex !== index) {
      this.swap(index, largestIndex);
      this.bubbleDown(largestIndex);
    }
  }
}

// 使用示例
const maxHeap = new MaxHeap();
maxHeap.insert(3);
maxHeap.insert(4);
maxHeap.insert(9);
maxHeap.insert(5);
maxHeap.insert(2);

console.log(maxHeap.extractMax()); // 输出: 9
console.log(maxHeap.extractMax()); // 输出: 5