数据结构堆的概念：像行李箱叠放一样的优先级管理

坐过高铁的人都知道，站台上总会有人急着挤上车，把大件行李往车厢连接处一塞，后来的人哪怕拿着小包也只能干等。这其实就像计算机里一种叫“堆”的数据结构——谁的优先级高，谁就先来。

堆是什么？用等车来理解

想象你在一个早高峰的地铁口，大家排队进站。系统不是按谁先到就让谁先进，而是谁最赶时间谁优先。这种“按优先级出队”的规则，背后靠的就是堆来实现。

堆本质上是一种特殊的完全二叉树，分为最大堆和最小堆。最大堆的根节点永远是最大的值，最小堆则相反。就像一堆行李从下往上叠，最上面那个总是最重或者最轻的，一眼就能挑出来。

堆怎么工作？就像快递分拣

你在电商平台下单后，系统会根据订单紧急程度安排发货。VIP客户的加急单会被提到最前面处理。这个排序过程，常常用堆来维护。

比如一个最小堆用来管理任务优先级：

      1
    /   \
   3     6
  / \   /
 5   9 7

每次取任务时，只看顶部的“1”，处理完后再把剩下的重新调整，确保下一个最小值浮到顶。这个过程叫做“堆化”，就像快递员不断整理包裹，保证最急的永远在最上面。

堆的实际应用场景

导航软件规划路线时，会用“堆”来快速选出当前距离最短的路径节点。Dijkstra 算法就是靠最小堆高效运行的。没有它，你等个路线可能要多花几秒，高峰期堵在路上可耗不起。

还有共享单车调度系统，哪个区域缺车最严重，就优先派车过去。这些判断背后也藏着堆的身影。它不声不响，却让城市运转更顺。

简单实现一个最小堆

用数组也能表示堆，父节点和子节点的位置有固定关系：第 i 个元素的左孩子是 2*i+1，右孩子是 2*i+2。这样存起来省空间，查起来也快。

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

    insert(val) {
        this.heap.push(val);
        this._heapifyUp();
    }

    _heapifyUp() {
        let idx = this.heap.length - 1;
        while (idx > 0) {
            let parentIdx = Math.floor((idx - 1) / 2);
            if (this.heap[parentIdx] <= this.heap[idx]) break;
            [this.heap[parentIdx], this.heap[idx]] = [this.heap[idx], this.heap[parentIdx]];
            idx = parentIdx;
        }
    }

    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._heapifyDown(0);
        return min;
    }

    _heapifyDown(idx) {
        const left = 2 * idx + 1;
        const right = 2 * idx + 2;
        let smallest = idx;

        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 !== idx) {
            [this.heap[idx], this.heap[smallest]] = [this.heap[smallest], this.heap[idx]];
            this._heapifyDown(smallest);
        }
    }
}

这段代码就像是一个自动分拣机，新来的任务插进去，最紧急的自动浮到顶，取走一个，剩下的立刻重新排队。

下次你在手机上看实时公交，等红绿灯时导航突然换了一条更快的路，别忘了，可能是某个堆正在后台默默帮你抢时间。