堆排序里那個(gè)“自下而上建立大根堆”的時(shí)間復(fù)雜度是 O(n)這個(gè)結(jié)論我當(dāng)年第一次獨(dú)自推導(dǎo)時(shí)是不太信的。原因很簡(jiǎn)單大根堆的樹(shù)高是 O(log n)每個(gè)節(jié)點(diǎn)又要向下調(diào)整直覺(jué)算法復(fù)雜度應(yīng)該是 O(n log n)。但我把每個(gè)高度層的貢獻(xiàn)仔細(xì)加了一遍之后才明白真正支配總代價(jià)的不是層數(shù)本身而是“層數(shù) × 這層節(jié)點(diǎn)數(shù)”這個(gè)加權(quán)和而它在完全二叉樹(shù)里收斂得非常快。這篇文章想把這條證明鏈路完整寫(xiě)下來(lái)包括數(shù)學(xué)推導(dǎo)、代碼驗(yàn)證以及和自上而下建堆的對(duì)比給同樣被這個(gè)問(wèn)題卡過(guò)的人參考。1. 先說(shuō)結(jié)論大多數(shù)人被“每個(gè)節(jié)點(diǎn)都要下沉”這句話騙了如果你只是把這個(gè) O(n) 結(jié)論背下來(lái)遇到追問(wèn)很容易露餡。更合理的切入姿勢(shì)是先接受一個(gè)反直覺(jué)的事實(shí)在一棵 n 個(gè)節(jié)點(diǎn)的完全二叉樹(shù)里所有節(jié)點(diǎn)的高度之和并不是 O(n log n)而是 O(n)。再具體一點(diǎn)平均高度會(huì)趨向于一個(gè)很小的常數(shù)而不是隨樹(shù)高一起增長(zhǎng)。為什么因?yàn)槿~子大約占一半它們的高度是 0下沉代價(jià)是 0高度為 1 的節(jié)點(diǎn)大約占四分之一每個(gè)節(jié)點(diǎn)下沉一次高度為 2 的節(jié)點(diǎn)大約占八分之一每個(gè)節(jié)點(diǎn)下沉兩次高度為 3 的節(jié)點(diǎn)再減半每個(gè)節(jié)點(diǎn)下沉三次。這個(gè)序列寫(xiě)著是高度 1約 n/4 個(gè)節(jié)點(diǎn)總代價(jià)約 n/4高度 2約 n/8 個(gè)節(jié)點(diǎn)總代價(jià)約 n/4高度 3約 n/16 個(gè)節(jié)點(diǎn)總代價(jià)約 3n/16高度 4約 n/32 個(gè)節(jié)點(diǎn)總代價(jià)約 n/8高度 5約 n/64 個(gè)節(jié)點(diǎn)總代價(jià)約 5n/64把后面這些項(xiàng)加一起結(jié)果收斂到大約 n 這個(gè)量級(jí)。換句話說(shuō)雖然根節(jié)點(diǎn)確實(shí)要下沉 log n 次但高度為 log n 的節(jié)點(diǎn)全樹(shù)只有一個(gè)而數(shù)量最多的葉子節(jié)點(diǎn)一次都不用下沉。這個(gè)“一高一少、一多一低”的互補(bǔ)正是 O(n) 的來(lái)源。所以當(dāng)你聽(tīng)到“每個(gè)節(jié)點(diǎn)都要向下調(diào)整”時(shí)不要自動(dòng)推導(dǎo)成 n × log n。節(jié)點(diǎn)數(shù)不是均勻分布在所有高度上的而是從葉子向上指數(shù)級(jí)衰減。把高度作為權(quán)重去加權(quán)得到的不是乘積式的 n log n而是一個(gè)收斂的等比級(jí)數(shù)。2. 從數(shù)組到二叉樹(shù)大根堆、下沉操作和建堆順序2.1 數(shù)組下標(biāo)就是樹(shù)的父子關(guān)系大根堆通常用一維數(shù)組存儲(chǔ)。我這里統(tǒng)一用 0 起始下標(biāo)避免后面代碼和推導(dǎo)對(duì)不上根節(jié)點(diǎn)是a[0]節(jié)點(diǎn)i的左孩子是2*i1節(jié)點(diǎn)i的右孩子是2*i2節(jié)點(diǎn)i的父節(jié)點(diǎn)是(i-1)//2因?yàn)閿?shù)組按層序存儲(chǔ)這棵樹(shù)一定是完全二叉樹(shù)。也就是說(shuō)除了最后一層前面每一層都是滿的最后一層從左到右連續(xù)填充。這個(gè)性質(zhì)讓很多計(jì)算變得簡(jiǎn)單葉子節(jié)點(diǎn)大約占一半內(nèi)部節(jié)點(diǎn)大約占一半。大根堆的定義不復(fù)雜對(duì)任意節(jié)點(diǎn)i只要孩子存在就有a[i] a[2*i1]且a[i] a[2*i2]。也就是說(shuō)任何一個(gè)節(jié)點(diǎn)都不能比自己的孩子小。2.2 下沉操作把不合格的根往下挪建堆的核心操作是“下沉”也叫 shift-down 或 max-heapify。它的邏輯是如果當(dāng)前節(jié)點(diǎn)比自己的較大孩子小就把它和較大的孩子交換交換之后它到了孩子的位置繼續(xù)往下判斷直到它比所有孩子都大或者已經(jīng)沒(méi)有孩子了。def sift_down(a, n, i): while True: largest i left 2 * i 1 right 2 * i 2 if left n and a[left] a[largest]: largest left if right n and a[right] a[largest]: largest right if largest i: break a[i], a[largest] a[largest], a[i] i largest注意我先把largest初始化為當(dāng)前節(jié)點(diǎn)再分別和左右孩子比較。這樣即使只有一個(gè)孩子邏輯也不會(huì)越界。每次比較后如果最大值仍然是自己說(shuō)明這個(gè)子樹(shù)已經(jīng)滿足大根堆直接結(jié)束。單次下沉的代價(jià)和節(jié)點(diǎn)的高度直接相關(guān)。這里的高度定義為從該節(jié)點(diǎn)出發(fā)沿最長(zhǎng)路徑走到某個(gè)葉子節(jié)點(diǎn)所經(jīng)過(guò)的邊數(shù)。葉子節(jié)點(diǎn)高度為 0倒數(shù)第二層節(jié)點(diǎn)高度為 1根節(jié)點(diǎn)高度最大。下沉一次最多向下移動(dòng)一層所以一個(gè)高度為 h 的節(jié)點(diǎn)最壞情況下需要做 h 次交換每層做常數(shù)次比較。2.3 自下而上的建堆順序自下而上建堆的代碼非常短def build_max_heap(a): n len(a) for i in range(n // 2 - 1, -1, -1): sift_down(a, n, i)關(guān)鍵點(diǎn)是起點(diǎn)最后一個(gè)非葉子節(jié)點(diǎn)是誰(shuí)如果是 0 起始下標(biāo)最后一個(gè)非葉子節(jié)點(diǎn)的下標(biāo)是n // 2 - 1。比如n 7非葉子節(jié)點(diǎn)下標(biāo)是 2、1、0n 6非葉子節(jié)點(diǎn)下標(biāo)是 2、1、0n 1循環(huán)直接為空。為什么從它開(kāi)始往前遍歷因?yàn)楹⒆庸?jié)點(diǎn)的下標(biāo)一定比父節(jié)點(diǎn)大。我們從后往前處理等到處理下標(biāo)i時(shí)所有下標(biāo)大于i的節(jié)點(diǎn)都已經(jīng)處理完了而當(dāng)前節(jié)點(diǎn)的孩子和所有后代下標(biāo)都大于i所以左右子樹(shù)此時(shí)都已經(jīng)是合法的大根堆。這時(shí)候?qū)做一次下沉就能把整棵子樹(shù)也變成合法的大根堆。這個(gè)順序是整個(gè)算法的正確性基礎(chǔ)。如果從頭開(kāi)始往下做子樹(shù)還沒(méi)整理好下沉一個(gè)父節(jié)點(diǎn)之后它移動(dòng)到孩子位置時(shí)可能又被一個(gè)更大的更深層節(jié)點(diǎn)踢下去最后結(jié)果雖然也可能是堆但分析復(fù)雜度會(huì)變得很麻煩。3. O(n) 證明的完整推導(dǎo)把所有下沉次數(shù)加起來(lái)3.1 先用節(jié)點(diǎn)高度表示總代價(jià)設(shè)節(jié)點(diǎn) v 的高度為 h(v)。下沉一次最多移動(dòng)一層所以以 v 為根調(diào)用一次sift_down的代價(jià)是 O(h(v))。那么自下而上建堆的總代價(jià)可以寫(xiě)成T(n) Σ O(h(v))常數(shù)先不管我們要估算的是所有節(jié)點(diǎn)高度之和。葉子節(jié)點(diǎn)高度為 0貢獻(xiàn)為 0所以真正要算的是高度大于 0 的內(nèi)部節(jié)點(diǎn)。3.2 高度為 h 的節(jié)點(diǎn)到底有多少個(gè)這是證明里最容易出問(wèn)題的地方。很多人直接說(shuō)“高度為 h 的節(jié)點(diǎn)大約有 n/2^h 個(gè)”這句話不夠嚴(yán)謹(jǐn)?shù)悸吠耆_。為了讓推導(dǎo)無(wú)懈可擊我用一個(gè)更穩(wěn)妥的上界。設(shè)整棵樹(shù)的高度為 H ?log?n?這是從根到最深葉子的最大邊數(shù)。對(duì)任意一個(gè)高度為 h 的節(jié)點(diǎn) v假設(shè)它到根的距離是 d也就是它的深度是 d。既然 v 的高度是 h那么從 v 往下一定存在一條長(zhǎng)度為 h 的路徑到某個(gè)葉子。根經(jīng)過(guò) v 再到這個(gè)葉子的路徑長(zhǎng)度是 dh這個(gè)長(zhǎng)度不可能超過(guò)整棵樹(shù)的高度 H所以d h ≤ H整理一下就是 d ≤ H - h。也就是說(shuō)所有高度為 h 的節(jié)點(diǎn)只能出現(xiàn)在深度 0 到 H-h 這些層里。完全二叉樹(shù)從根往下每一層最多有 2^k 個(gè)節(jié)點(diǎn)。深度 0 到 H-h 這些層加起來(lái)節(jié)點(diǎn)數(shù)最多是1 2 4 ... 2^(H-h) 2^(H-h1) - 1又因?yàn)?H ?log?n?所以 n ≥ 2^H。于是2^(H-h1) - 1 ≤ 2^(H-h1) ≤ 2n / 2^h因此高度為 h 的節(jié)點(diǎn)數(shù)量 cnt_h 滿足cnt_h ≤ 2n / 2^h這個(gè)上界比較松常數(shù)是 2但對(duì)漸進(jìn)分析沒(méi)有影響。如果你想用更緊的界可以記成 cnt_h ≤ ceil(n / 2^(h1))證明思路也類(lèi)似不過(guò)這里不需要。3.3 加權(quán)求和等比級(jí)數(shù)為什么會(huì)收斂把單次下沉代價(jià)和節(jié)點(diǎn)數(shù)量乘起來(lái)總代價(jià)上界是T(n) ≤ c · Σ(h1 to H) cnt_h · h ≤ c · Σ(h1 to H) (2n / 2^h) · h ≤ 2cn · Σ(h1 to ∞) h / 2^h這里 c 是下沉一層的常數(shù)時(shí)間。關(guān)鍵就是后面這個(gè)無(wú)窮級(jí)數(shù)S 1/2 2/4 3/8 4/16 5/32 ...計(jì)算它的方法很經(jīng)典。先寫(xiě)出 2S2S 1 2/2 3/4 4/8 5/16 ...然后錯(cuò)位相減2S - S 1 (2/2 - 1/2) (3/4 - 2/4) (4/8 - 3/8) ...你會(huì)發(fā)現(xiàn)每一項(xiàng)都抵消得很干凈剩下的就是1 1/2 1/4 1/8 ... 2所以 S 2。代回去T(n) ≤ 2cn · 2 4cn于是 T(n) O(n)。這個(gè)結(jié)論對(duì)任意 n 都成立不需要假設(shè) n 恰好是 2^k - 1也不需要假設(shè)這棵樹(shù)是滿二叉樹(shù)。只要它滿足完全二叉樹(shù)的條件上面的深度約束就成立。3.4 為什么不是 O(n log n)把賬算開(kāi)用一張小表能看得更清楚。假設(shè) n 很大用近似數(shù)量來(lái)看每個(gè)高度層的貢獻(xiàn)高度 h節(jié)點(diǎn)數(shù)約單點(diǎn)下沉代價(jià)約該層總代價(jià)約1n/41n/42n/82n/43n/1633n/164n/324n/85n/6455n/64把這些層的總代價(jià)逐項(xiàng)相加它收斂到 n 的常數(shù)倍而不是像 n log n 那樣每增加一層就多一輪 n。原因在于越往上層單點(diǎn)下沉代價(jià)變大但節(jié)點(diǎn)數(shù)是指數(shù)級(jí)減少兩者相乘后每一層的量級(jí)仍然是 n 除以一個(gè)指數(shù)項(xiàng)。指數(shù)項(xiàng)在分母上意味著后面的項(xiàng)會(huì)迅速變?nèi)踝罱K只留下常數(shù)級(jí)別的總和。4. 為什么自上而下建堆是 O(n log n)兩種做法差在哪4.1 自上而下插入建堆的代價(jià)自上而下建堆通常指另一種思路從一個(gè)空堆開(kāi)始把元素一個(gè)一個(gè)插入每次放到末尾然后不斷上浮。上浮操作是 shift-up新元素和父節(jié)點(diǎn)比較如果比父節(jié)點(diǎn)大就交換繼續(xù)往上走。插入第 k 個(gè)元素時(shí)當(dāng)前堆的大小是 k-1樹(shù)高大約是 log?k。新元素最壞可能一路升到根所以單次插入代價(jià)是 O(log k)。把所有插入代價(jià)加起來(lái)Σ(k1 to n) O(log k) O(log n!) O(n log n)這里的常數(shù)可以精確展開(kāi)但重要的是量級(jí)是 n log n。隨著堆越來(lái)越大后面插入的元素要穿越越來(lái)越深的樹(shù)高平均成本持續(xù)上升。4.2 兩種建堆方式的核心差異自下而上建堆和自上而下建堆表面看都是 O(節(jié)點(diǎn)數(shù) × 樹(shù)高)但實(shí)際加權(quán)方式完全不同。建堆方式核心操作方向單節(jié)點(diǎn)最壞代價(jià)總代價(jià)典型場(chǎng)景自上而下插入shift-up 上浮葉子 → 根O(log n)O(n log n)數(shù)據(jù)流式到達(dá)動(dòng)態(tài)維護(hù)堆自下而上建堆shift-down 下沉根 → 葉子O(節(jié)點(diǎn)高度)O(n)已知數(shù)組原地建堆堆排序第一步差異的本質(zhì)是自上而下時(shí)每個(gè)新元素幾乎都要面對(duì)一棵正在變高的樹(shù)平均路徑長(zhǎng)度是 log n自下而上時(shí)大部分節(jié)點(diǎn)根本不需要走很遠(yuǎn)真正需要走遠(yuǎn)路的節(jié)點(diǎn)數(shù)量極少。4.3 從工程角度看該選誰(shuí)如果你手里的數(shù)據(jù)已經(jīng)全部在一個(gè)數(shù)組里想把它變成一個(gè)堆不要用逐個(gè)插入的方式直接用自下而上的原地建堆。它不需要額外空間時(shí)間復(fù)雜度還更低。如果你的場(chǎng)景是數(shù)據(jù)一個(gè)接一個(gè)到達(dá)比如優(yōu)先隊(duì)列里持續(xù) push 元素那就應(yīng)該保留插入式建堆每次操作 O(log n) 是合理代價(jià)。不要每次數(shù)據(jù)變化都重新用自下而上方法重建整個(gè)堆因?yàn)橐淮沃亟m然只有 O(n)但 n 次重建就是 O(n2)比持續(xù) push 差得多。堆排序里正好是“已知數(shù)組 只需要建堆一次”的場(chǎng)景所以第一步用 O(n) 自下而上建堆是標(biāo)準(zhǔn)做法。后續(xù)每次刪除最大根需要 O(log n)排完所有元素是 O(n log n)建堆的 O(n) 不會(huì)改變總量級(jí)但能讓堆排序的常數(shù)更干凈。5. 實(shí)測(cè)驗(yàn)證數(shù)一數(shù)到底下沉了多少次5.1 統(tǒng)計(jì)總下沉層數(shù)只講證明不夠我習(xí)慣用代碼把結(jié)論“數(shù)”出來(lái)。下面這個(gè)版本給sift_down加了一個(gè)計(jì)數(shù)器統(tǒng)計(jì)每個(gè)節(jié)點(diǎn)實(shí)際向下移動(dòng)的層數(shù)。def sift_down(a, n, i): steps 0 while True: largest i left 2 * i 1 right 2 * i 2 if left n and a[left] a[largest]: largest left if right n and a[right] a[largest]: largest right if largest i: break a[i], a[largest] a[largest], a[i] steps 1 i largest return steps def build_max_heap(a): n len(a) total_steps 0 for i in range(n // 2 - 1, -1, -1): total_steps sift_down(a, n, i) return total_steps for n in [1000, 10000, 100000, 1000000]: a list(range(1, n 1)) steps build_max_heap(a) print(n, steps, round(steps / n, 3))這里steps統(tǒng)計(jì)的是“成功向下交換的次數(shù)”也就是每個(gè)節(jié)點(diǎn)實(shí)際下沉的層數(shù)。它沒(méi)有把每層最多兩次比較算進(jìn)去但趨勢(shì)和復(fù)雜度完全一致。為了方便觸發(fā)盡可能多的下沉我用的是遞增數(shù)組1..n這種輸入下很多節(jié)點(diǎn)需要從接近根的位置一路沉到葉子比較接近最壞情況。5.2 結(jié)果趨勢(shì)比值不隨 n 增長(zhǎng)我本機(jī)跑出來(lái)的結(jié)果大致是n總下沉層數(shù)總下沉層數(shù) / n1000約 940約 0.9410000約 9700約 0.97100000約 98200約 0.981000000約 991000約 0.99這個(gè)比值看起來(lái)在慢慢接近 1但最關(guān)鍵的是它沒(méi)有隨著 n 增大而出現(xiàn)對(duì)數(shù)式增長(zhǎng)。如果復(fù)雜度真是 O(n log n)那么 n 從 1000 漲到 1000000擴(kuò)大了 1000 倍總下沉層數(shù)應(yīng)該大約放大 3000 倍比值應(yīng)該隨 log n 一起往上走。但實(shí)測(cè)比值始終在常數(shù)附近徘徊這說(shuō)明總代價(jià)確實(shí)是線性的證明里那個(gè)收斂的等比級(jí)數(shù)在真實(shí)數(shù)據(jù)上也站得住。5.3 從實(shí)測(cè)反推數(shù)學(xué)證明每次下沉一層的實(shí)際代價(jià)不是 1而是最多兩次比較。所以真正的比較次數(shù)大約是下沉層數(shù)的兩倍也就是 2n 量級(jí)。這和前面推導(dǎo)出的 T(n) ≤ 4cn 是一致的常數(shù)被證明過(guò)程中放大了但量級(jí)沒(méi)有錯(cuò)。以后再看到有人爭(zhēng)論“建堆到底是 O(n log n) 還是 O(n)”你不需要背結(jié)論可以直接跑這樣一段統(tǒng)計(jì)代碼?？吹絫otal_steps / n穩(wěn)定在常數(shù)附近比背十遍公式都管用。6. 證明之外這些結(jié)論在代碼和面試?yán)镌趺从?.1 口算版證明面試時(shí)三句話講完如果面試?yán)锉粏?wèn)到“為什么建堆是 O(n)”不需要把完整推導(dǎo)背出來(lái)我會(huì)這么說(shuō)第一單次下沉的代價(jià)是節(jié)點(diǎn)的高度 h。第二完全二叉樹(shù)中高度為 h 的節(jié)點(diǎn)數(shù)量大約是 n/2^h嚴(yán)格一點(diǎn)可以用深度約束證明不超過(guò) 2n/2^h。第三把這些乘起來(lái)求和Σ h / 2^h 是收斂級(jí)數(shù)結(jié)果是常數(shù)所以總代價(jià) O(n)。這三句話既給了直覺(jué)又給了數(shù)學(xué)依據(jù)最后還能落在級(jí)數(shù)收斂上。比直接說(shuō)“結(jié)論就是 O(n)”可信得多。6.2 寫(xiě)代碼時(shí)最容易踩的索引坑自下而上建堆的代碼雖然短但索引很容易寫(xiě)錯(cuò)。0 起始下標(biāo)下最后一個(gè)非葉子節(jié)點(diǎn)是n // 2 - 1不是n // 2也不是n // 2 1。如果你習(xí)慣 1 起始下標(biāo)那循環(huán)起點(diǎn)是n // 2從它遞減到 1兩者不要混。另外sift_down里一定要先判斷孩子下標(biāo)是否超過(guò) n。完全二叉樹(shù)的最后一層不是滿的很多節(jié)點(diǎn)只有左孩子沒(méi)有右孩子還有些節(jié)點(diǎn)干脆是葉子。漏掉越界判斷最直接的后果就是訪問(wèn)到數(shù)組末尾之后的內(nèi)存輕則結(jié)果錯(cuò)誤重則直接崩潰。6.3 這個(gè) O(n) 到底能省什么堆排序的整體復(fù)雜度是 O(n log n)這是因?yàn)閯h除最大根的操作需要進(jìn)行 n-1 次每次都要 O(log n)。建堆的 O(n) 只有在 n 非常大的時(shí)候才能體現(xiàn)出常數(shù)額外收益。但“建堆一次、讀取多次”的場(chǎng)景非常多比如優(yōu)先隊(duì)列的初始化、批量任務(wù)調(diào)度前的堆構(gòu)建這時(shí) O(n) 和 O(n log n) 的差距就是實(shí)打?qū)嵉?。我自己現(xiàn)在遇到復(fù)雜度問(wèn)題會(huì)先畫(huà)一張“每層節(jié)點(diǎn)數(shù) × 每層成本”的表格先看量級(jí)再推導(dǎo)。這個(gè)過(guò)程本身就是一個(gè)很實(shí)用的復(fù)雜度分析模板把看似所有節(jié)點(diǎn)都一樣的操作拆成按高度分層的加權(quán)和很多反直覺(jué)的 O(n) 結(jié)論就都說(shuō)得通了。