JavaScript 二叉堆

二叉堆是一种特殊的树形数据结构，它满足以下特性：

• 每个节点的值都大于或等于其子节点的值（最大堆）
• 或者每个节点的值都小于或等于其子节点的值（最小堆）

二叉堆通常使用数组来实现，这样可以高效地进行插入、删除和查找操作。

二叉堆的基本操作

插入元素

插入元素时，需要将新元素添加到数组的末尾，然后通过“上浮”操作使其满足堆的性质。具体步骤如下：

1. 将新元素添加到数组的末尾。
2. 检查新元素是否违反了堆的性质（例如，在最大堆中，新元素是否大于其父节点）。如果违反，则交换新元素与父节点的位置。
3. 重复步骤2，直到新元素不再违反堆的性质。

删除元素

删除元素时，通常删除的是堆顶元素（根节点），然后将最后一个元素移动到根节点位置，并通过“下沉”操作使其满足堆的性质。具体步骤如下：

1. 将最后一个元素移动到根节点位置。
2. 检查当前根节点是否违反了堆的性质（例如，在最大堆中，根节点是否小于其子节点）。如果违反，则与较大的子节点交换位置。
3. 重复步骤2，直到当前根节点不再违反堆的性质。

构建堆

构建一个堆的过程可以从一个无序数组开始。构建堆的基本思想是将数组中的每个元素依次插入到堆中。具体步骤如下：

1. 初始化一个空的堆。
2. 遍历数组中的每个元素，并将其插入到堆中。

另一种更高效的构建堆的方法是从最后一个非叶子节点开始，依次执行下沉操作。这样可以在 O(n) 时间复杂度内完成堆的构建。

二叉堆的实现

下面是一个简单的 JavaScript 实现二叉堆的代码示例：

// www.javascriptcn.com code example
class BinaryHeap {
    constructor(comparator = (a, b) => a > b) {
        this.heap = [];
        this.comparator = comparator;
    }

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

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

    // 删除元素
    extract() {
        const value = this.heap[0];
        const lastValue = this.heap.pop();
        if (this.heap.length > 0) {
            this.heap[0] = lastValue;
            this.sinkDown(0);
        }
        return value;
    }

    // 下沉操作
    sinkDown(index) {
        const length = this.heap.length;
        const element = this.heap[index];

        while (true) {
            let childIndex1 = 2 * index + 1;
            let childIndex2 = 2 * index + 2;
            let swap = null;

            if (childIndex1 < length) {
                if (this.comparator(element, this.heap[childIndex1])) {
                    swap = childIndex1;
                }
            }

            if (childIndex2 < length) {
                if (
                    (swap === null && this.comparator(element, this.heap[childIndex2])) ||
                    (swap !== null && this.comparator(this.heap[childIndex1], this.heap[childIndex2]))
                ) {
                    swap = childIndex2;
                }
            }

            if (swap === null) break;
            [this.heap[index], this.heap[swap]] = [this.heap[swap], this.heap[index]];
            index = swap;
        }
    }

    // 构建堆
    buildHeap(array) {
        this.heap = array.slice();
        for (let i = Math.floor(this.heap.length / 2); i >= 0; i--) {
            this.sinkDown(i);
        }
    }
}

// 示例：使用最大堆
const maxHeap = new BinaryHeap((a, b) => a > b);
maxHeap.insert(3);
maxHeap.insert(1);
maxHeap.insert(4);
maxHeap.insert(2);

console.log(maxHeap.heap); // 输出: [4, 2, 3, 1]

// 示例：使用最小堆
const minHeap = new BinaryHeap((a, b) => a < b);
minHeap.insert(3);
minHeap.insert(1);
minHeap.insert(4);
minHeap.insert(2);

console.log(minHeap.heap); // 输出: [1, 2, 4, 3]

以上代码展示了如何使用 JavaScript 实现一个通用的二叉堆类，并提供了插入、删除、构建等基本操作。可以根据实际需求调整比较函数来实现最大堆或最小堆。