⛰️ 堆 Heap 可视化

堆是完全二叉树：大顶堆每个节点 ≥ 子节点。用数组存储，索引 i 的孩子是 2i+1 和 2i+2

欢迎！体验大顶堆的插入（上浮）和删除堆顶（下沉）

堆排序：反复取出堆顶 → 得到有序序列

堆排序思想：
① 建堆：把数组调整为大顶堆（自底向上下沉）；
② 排序：每次把堆顶（最大值）与末尾交换，缩小堆再下沉，重复 n-1 次；
③ 结果：数组从小到大有序。时间复杂度 O(n log n)，原地排序。
点击按钮观看堆排序全过程

JavaScript 实现（大顶堆）

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

    // 父节点和子节点索引
    parent(i) { return (i - 1) >> 1; }
    left(i) { return 2 * i + 1; }
    right(i) { return 2 * i + 2; }

    // 插入：末尾添加，然后上浮 - O(log n)
    insert(val) {
        this.heap.push(val);
        let i = this.heap.length - 1;
        while (i > 0) {
            const p = this.parent(i);
            if (this.heap[p] >= this.heap[i]) break;
            [this.heap[p], this.heap[i]] = [this.heap[i], this.heap[p]];
            i = p;
        }
    }

    // 取出堆顶：与末尾交换，弹出，然后下沉 - O(log n)
    extractMax() {
        if (!this.heap.length) return null;
        const max = this.heap[0];
        this.heap[0] = this.heap.pop();
        this._siftDown(0);
        return max;
    }

    // 下沉：与较大的孩子交换 - O(log n)
    _siftDown(i) {
        const n = this.heap.length;
        while (true) {
            let largest = i;
            const l = this.left(i), r = this.right(i);
            if (l < n && this.heap[l] > this.heap[largest]) largest = l;
            if (r < n && this.heap[r] > this.heap[largest]) largest = r;
            if (largest === i) break;
            [this.heap[i], this.heap[largest]] = [this.heap[largest], this.heap[i]];
            i = largest;
        }
    }

    // 堆排序：原地排序，O(n log n)
    static heapSort(arr) {
        const h = new MaxHeap();
        h.heap = arr.slice();
        const n = arr.length;
        // 建堆：从最后一个非叶节点开始下沉
        for (let i = (n >> 1) - 1; i >= 0; i--) h._siftDown(i);
        // 反复交换堆顶与末尾，缩小堆范围再下沉
        for (let end = n - 1; end > 0; end--) {
            [h.heap[0], h.heap[end]] = [h.heap[end], h.heap[0]];
            h._siftDownLimit(0, end);
        }
        return h.heap;
    }

    // 带范围限制的下沉（堆排序专用）
    _siftDownLimit(i, end) {
        while (true) {
            let largest = i;
            const l = this.left(i), r = this.right(i);
            if (l < end && this.heap[l] > this.heap[largest]) largest = l;
            if (r < end && this.heap[r] > this.heap[largest]) largest = r;
            if (largest === i) break;
            [this.heap[i], this.heap[largest]] = [this.heap[largest], this.heap[i]];
            i = largest;
        }
    }
}

时间复杂度分析

操作时间复杂度说明
插入 InsertO(log n)上浮最多走树高
删除堆顶 ExtractMaxO(log n)下沉最多走树高
查看堆顶 PeekO(1)heap[0] 就是最大值
建堆 BuildHeapO(n)自底向上下沉（数学可证）
堆排序 HeapSortO(n log n)原地排序，不稳定

实际应用场景

  • 🏆 优先队列：操作系统任务调度、事件驱动
  • 📈 Top-K 问题：维护大小为 K 的最小堆，找最大 K 个元素
  • 📊 堆排序：O(n log n) 原地排序算法
  • 🗺️ Dijkstra 最短路：优先队列取距离最小节点
  • ⏰ 定时器：维护最近到期的任务