devpoint.cn

在 JavaScript 中，可以通过数组来实现一个二叉堆。二叉堆分为最大堆和最小堆两种类型，本问将以最大堆为例子。

一个二叉堆可以看做是一颗完全二叉树，每个节点的值都大于等于其子节点的值（对于最大堆而言）。因此，在使用数组来实现二叉堆时，可以使用数组下标来表示完全二叉树的节点，并满足以下规则：

1. 对于任意节点 i，其左子节点的下标为 2i+1，右子节点的下标为 2i+2。
2. 对于任意节点 i，其父节点的下标为 Math.floor((i-1)/2)。

接下来，可以使用数组来实现一个最大堆。具体而言，可以定义一个数组 arr 来保存堆的元素，并定义一些方法来实现堆的常见操作，如插入元素、删除堆顶元素等。下面是一个简单的实现示例：

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

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

    // 删除堆顶元素
    extractMax() {
        const max = this.heap[0];
        const end = this.heap.pop();

        if (this.heap.length > 0) {
            this.heap[0] = end;
            this.sinkDown(0);
        }

        return max;
    }

    // 上浮操作
    bubbleUp(index) {
        const element = this.heap[index];
        while (index > 0) {
            const parentIndex = Math.floor((index - 1) / 2);
            const parent = this.heap[parentIndex];
            if (element <= parent) {
                break;
            }
            this.heap[parentIndex] = element;
            this.heap[index] = parent;
            index = parentIndex;
        }
    }

    // 下沉操作
    sinkDown(index) {
        const left = 2 * index + 1;
        const right = 2 * index + 2;
        let largest = index;

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

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

        if (largest !== index) {
            const temp = this.heap[index];
            this.heap[index] = this.heap[largest];
            this.heap[largest] = temp;
            this.sinkDown(largest);
        }
    }
}

在上述代码中，MaxHeap 类定义了一个数组 heap 来保存堆的元素，同时实现了 insert、extractMax、bubbleUp 和 sinkDown 方法，分别用于插入元素、删除堆顶元素、上浮操作和下沉操作。

在 bubbleUp 方法中，使用循环来不断将新插入的元素上浮，直到满足堆的条件；sinkDown 方法中，首先找出当前节点的左子节点和右子节点，然后将当前节点与两个子节点中的最大值进行比较，如果当前节点的值小于最大值，则交换两个节点的值，并递归进行下沉操作，直到满足堆的条件。

上面定义类的使用方式如下：

const maxHeap = new MaxHeap();

maxHeap.insert(26);
maxHeap.insert(103);
maxHeap.insert(721);
maxHeap.insert(911);
maxHeap.insert(202);

console.log(maxHeap.heap); // [ 911, 721, 103, 26, 202 ]

const max = maxHeap.extractMax();
console.log(max); // 911
console.log(maxHeap.heap); // [ 721, 202, 103, 26 ]

上面代码首先创建了一个最大堆 maxHeap，插入了一些元素。然后，调用 extractMax 方法来删除堆顶元素，得到最大值并打印。最后，打印修改后的堆结构，可以看到堆顶的元素已经被删除并且堆的结构已经满足最大堆的条件。