JavaScript实现最大堆（Max Heap）的完整指南 | 优先队列数据结构

最大堆（Max Heap）是一种特殊的二叉树结构，其中每个父节点的值都大于或等于其子节点的值。最大堆通常用于实现优先队列。下面是一个使用 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;
    }

    // 判断堆是否为空
    isEmpty() {
        return this.heap.length === 0;
    }
}

// 示例用法
const maxHeap = new MaxHeap();
maxHeap.insert(10);
maxHeap.insert(5);
maxHeap.insert(15);
maxHeap.insert(3);
maxHeap.insert(7);

console.log(maxHeap.extractMax()); // 输出: 15
console.log(maxHeap.extractMax()); // 输出: 10
console.log(maxHeap.extractMax()); // 输出: 7

代码说明：

1. MaxHeap 类：定义了最大堆的数据结构。
2. getParentIndex、getLeftChildIndex、getRightChildIndex：用于获取父节点和子节点的索引。
3. swap：交换两个节点的值。
4. insert：插入新元素并调用 heapifyUp 来维护堆的性质。
5. heapifyUp：上浮操作，确保新插入的元素不会破坏堆的性质。
6. extractMax：删除并返回堆顶元素，然后调用 heapifyDown 来维护堆的性质。
7. heapifyDown：下沉操作，确保堆顶元素被删除后，堆的性质仍然保持。
8. peek：获取堆顶元素但不删除。
9. size：获取堆的大小。
10. isEmpty：判断堆是否为空。

时间复杂度：

• 插入操作 (insert)：O(log n)
• 删除堆顶元素 (extractMax)：O(log n)
• 获取堆顶元素 (peek)：O(1)

这个实现是一个基础的最大堆，适用于大多数需要优先队列的场景。你可以根据具体需求对其进行扩展或优化。