最小堆和最大堆实现详解 日常维护方法与实用案例

最小堆和最大堆的基本概念

堆是一种特殊的完全二叉树结构，常用于高效实现优先队列。最小堆中，父节点的值总是小于或等于子节点；最大堆则相反，父节点的值总是大于或等于子节点。这种性质让堆在查找最小或最大元素时非常高效。

堆的数组表示

虽然堆是树形结构，但通常用数组来存储，节省空间且便于索引。对于下标从0开始的数组，节点i的左孩子是2*i+1，右孩子是2*i+2，父节点是(i-1)/2。这种方式让树的遍历变得简单直接。

最小堆的实现

构建最小堆的关键是“下沉”（heapify down）操作。当根节点被取出后，最后一个元素移到根位置，然后不断与较小的子节点交换，直到满足最小堆性质。

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

    insert(val) {
        this.heap.push(val);
        this._bubbleUp(this.heap.length - 1);
    }

    extractMin() {
        if (this.heap.length === 0) return null;
        if (this.heap.length === 1) return this.heap.pop();

        const min = this.heap[0];
        this.heap[0] = this.heap.pop();
        this._heapify(0);
        return min;
    }

    _bubbleUp(index) {
        while (index > 0) {
            const parentIndex = Math.floor((index - 1) / 2);
            if (this.heap[parentIndex] <= this.heap[index]) break;
            [this.heap[parentIndex], this.heap[index]] = [this.heap[index], this.heap[parentIndex]];
            index = parentIndex;
        }
    }

    _heapify(index) {
        const left = 2 * index + 1;
        const right = 2 * index + 2;
        let smallest = index;

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

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

        if (smallest !== index) {
            [this.heap[smallest], this.heap[index]] = [this.heap[index], this.heap[smallest]];
            this._heapify(smallest);
        }
    }
}

最大堆的实现

最大堆和最小堆结构相似，区别在于比较方向。插入和删除时，确保父节点始终不小于子节点。

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

    insert(val) {
        this.heap.push(val);
        this._bubbleUp(this.heap.length - 1);
    }

    extractMax() {
        if (this.heap.length === 0) return null;
        if (this.heap.length === 1) return this.heap.pop();

        const max = this.heap[0];
        this.heap[0] = this.heap.pop();
        this._heapify(0);
        return max;
    }

    _bubbleUp(index) {
        while (index > 0) {
            const parentIndex = Math.floor((index - 1) / 2);
            if (this.heap[parentIndex] >= this.heap[index]) break;
            [this.heap[parentIndex], this.heap[index]] = [this.heap[index], this.heap[parentIndex]];
            index = parentIndex;
        }
    }

    _heapify(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) {
            [this.heap[largest], this.heap[index]] = [this.heap[index], this.heap[largest]];
            this._heapify(largest);
        }
    }
}

实际应用场景

最小堆常用于实现任务调度系统，比如操作系统中的短作业优先策略。谁的执行时间最短，谁就先被处理。最大堆则适合排行榜场景，比如实时显示Top 10热门商品，每次只需要拿到当前最大的那个值。

再比如，你想找出一个数据流中第k大的数，用一个大小为k的最小堆就能轻松搞定。新来的数如果比堆顶大，就替换进去，再调整。这样堆里始终保留着最大的k个数，堆顶就是答案。