八年前，一個前端工程師在面試現(xiàn)場被問到："給你一個亂序數(shù)組，怎么最快找出前K大的元素？"他支支吾吾說了排序，面試官搖頭。后來才知道，有個叫"堆"的數(shù)據(jù)結(jié)構(gòu)，能在O(n)時間內(nèi)原地建堆，每次取極值只要O(log n)。今天這段JavaScript代碼，就是當(dāng)年那個問題的標(biāo)準(zhǔn)答案。

這段實(shí)現(xiàn)的核心是個叫BinaryHeap的類，它只做一件事：維護(hù)一個"父節(jié)點(diǎn)總比子節(jié)點(diǎn)優(yōu)先級高"的不變式。構(gòu)造函數(shù)接收兩個參數(shù)——一個初始數(shù)組和一個優(yōu)先級比較函數(shù)。有意思的是，它不做類型檢查，注釋里寫著"no types here in JS, so we trust"，這種信任在2024年的TypeScript時代反而顯得稀缺。

堆的魔法藏在兩個私有方法里。#heapifyUp負(fù)責(zé)插入時的上?。盒略叵葋G到數(shù)組末尾，然后不斷和父節(jié)點(diǎn)比較，優(yōu)先級更高就交換，直到找到合適位置。時間復(fù)雜度O(log n)，遞歸實(shí)現(xiàn)消耗O(log n)?？臻g，改成循環(huán)能壓到O(1)。#heapifyDown則處理刪除時的下沉：把末尾元素提到根節(jié)點(diǎn)，然后和左右孩子比，誰優(yōu)先級高跟誰換，一路沉到該去的地方。

最反直覺的是#buildHeapInPlace。直覺上建堆應(yīng)該逐個插入，每次O(log n)，總復(fù)雜度O(n log n)。但這段代碼從中間往前遍歷，對每個非葉子節(jié)點(diǎn)做一次下沉。數(shù)學(xué)上，高度為h的節(jié)點(diǎn)最多有?n/2^(h+1)?個，每個下沉最多h步，求和后收斂到O(n)。這種"從底向上"的策略，是堆排序能打敗普通排序的關(guān)鍵。

公開接口很克制：push和pop都是O(log n)，數(shù)組長度小于2時直接跳過堆化。代碼截斷在pop方法中間，但已足夠看出設(shè)計意圖——用私有字段封裝內(nèi)部狀態(tài)，用函數(shù)參數(shù)解耦優(yōu)先級邏輯，不硬編碼大小比較。這種靈活性讓同一個類既能當(dāng)最小堆也能當(dāng)最大堆，全看調(diào)用者怎么定義"更高優(yōu)先級"。

在實(shí)際工程里，這種結(jié)構(gòu)支撐著任務(wù)調(diào)度、合并K個有序流、Dijkstra算法里的優(yōu)先隊列。V8引擎的定時器、Node.js的事件循環(huán)、React的調(diào)度器，底層都有它的影子。當(dāng)你下次寫setTimeout時，可以想想：你的回調(diào)正在某個二叉堆里等著被喚醒呢。