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

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

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

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

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

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