1、堆與敗者樹比較-道經典的面試題：如何從N個數中選出最大（小）的n個數？這個問題我前前后后考慮了有快一年了，也和不少人討論過。據我得到的消息，Google和微軟 都面過這道題。這道題可能很多人都聽說過，或者知道答案（所謂的“堆”），不過我想把我的答 案寫出來。我的分析也許存有漏洞，以交流為目的。但這是一個滿復雜的問題，蠻有趣的。看完 本文，也許會啟發你一些沒有想過的解決方案（我一直認為堆也許不是最高效的算法）。在本文 中，將會一直以尋找n個最“大”的數為分析例子，以便統一。注：本文寫得會比較細節一些，以 便于絕大多數人都能看懂，別嫌我羅嗦:）我很不確定多少人有耐心看完本文！Naive方法：首先，

2、我們假設n和N都是內存可容納的，也就是說N個數可以一次load到內存里存放在 數組里（如果非要存在鏈表估計又是另一個challenging的問題了）。從最簡單的情況開始，如 果n=1，那么沒有任何疑惑，必須要進行N-1次的比較才能得到最大的那個數，直接遍歷N個 數就可以了。如果n=2呢？當然，可以直接遍歷2遍N數組，第一遍得到最大數maxi,但是 在遍歷第二遍求第二大數max2的時候，每次都要判斷從N所取的元素的下標不等于maxi的 下標，這樣會大大增加比較次數。對此有一個解決辦法，可以以maxi為分割點將N數組分成 前后兩部分，然后分別遍歷這兩部分得到兩個“最大數”，然后二者取一得到max2

3、。也可以遍歷一遍就解決此問題，首先維護兩個元素maxi，max2（max1=max2），取到N 中的一個數以后，先和maxi比，如果比maxi大（則肯定比max2大），直接替換maxi，否 則再和max2比較確定是否替換max2。采用類似的方法，對于n=2，3，4一樣可以處理。 這樣的算法時間復雜度為O（nN）。當n越來越大的時候（不可能超過N/2，否則可以變成是找 N-n個最小的數的對偶問題），這個算法的效率會越來越差。但是在n比較小的時候（具體多小 不好說），這個算法由于簡單，不存在遞歸調用等系統損耗，實際效率應該很不錯就如同排序的 時候口筆口薪隙淌保口捎彌苯硬迦肱判蚧峋口咝B?堆：當n較

4、大的時候采用什么算法呢？首先我們分析上面的算法，當從N中取出一個新的數m 的時候，它需要依次和maxi，max2，max3max n比較，一直找到一個比m小的max x，就用m來替換max x，平均比較次數是n/2。可不可以用更少的比較次數來實現替換呢？最直觀 的方法是，也就是網上文章比較推崇的堆。堆有這么一些好處：i.它是一個完全二叉樹，樹的深 度是相同節點的二叉樹中最少的，維護效率較高；2.它可以通過數組來實現，而且父節點p與左 右子節l，r點的數組下標的關系是sl = 2*sp+i和sr = 2*sp+2。在計算機中2*sp這樣的運 算可以用一個左移i位操作來實現，十分高效。再加上數組可

5、以隨機存取，效率也很高。3.堆的 Extract操作，也就是將堆頂拿走并重新維護堆的時間復雜度是O （logn），這里n是堆的大小。具體到我們的問題，如何具體實現呢？首先開辟一個大小為n的數組區A，從N中讀入n 個數填入到A中，然后將A維護成一個小頂堆（即堆頂A0中存放的是A中最小的數）。然后從 N中取出下一個數，即第n+1個數m，將m與堆頂A0比較，如果mn，則最大的n個數肯定在這j個數中，則問題變成在這j個數中 找出n個最大的數；否則如果jn，則這j個數肯定是n個最大的數的一部分，而剩下的j-n個 數在小于等于軸的那一部分中，同樣可遞歸處理。令人愉悅的是，這個算法的平均復雜度是O（N）的。

6、怎么樣？比堆的O（Nlogn）可能會好 一些吧？！（n如果比較大肯定會好）需要注意的是，這里的時間復雜度是平均意義上的，在最壞情況下，每次分割都分割成1： N-2,這種情況下的時間復雜度為O（n）。但是我們還有殺手銅，可以有一個在最壞情況下時間 復雜度為O（N）的算法，這個算法是在分割數列的時候保證會按照比較均勻的比例分割，at least 3n/10-6。具體細節我就不再說了，感興趣的人參考算法導論（Introduction to Algorithms第二 版第九章 “Medians and Orders Statistics）。還是那個結論，堆不見得會是最優的。本文快要結束了，但是還有一個

7、問題：如果N非常大，存放在磁盤上，不能一次裝載進內存呢？ 怎么辦？對于介紹的Naive方法，堆，敗者樹等等，依然適用，需要注意的就是每次從磁盤上 盡量多讀一些數到內存區，然后處理完之后再讀入一批。減少IO次數，自然能夠提高效率。而 對于類快速排序方法，稍微要麻煩一些：分批讀入，假設是M個數，然后從這M個數中選出n 個最大的數緩存起來，直到所有的N個數都分批處理完之后，再將各批次緩存的n個數合并起 來再進行一次類快速排序得到最終的n個最大的數就可以了。在運行過程中，如果緩存數太多， 可以不斷地將多個緩存合并，保留這些緩存中最大的n個數即可。由于類快速排序的時間復雜 度是O（N），這樣分批處理再合并的辦法，依然有極大的可能會比堆和敗者樹更優。當然，在 空間上會占用較多的內存。總結：對于這個問題，我想了很多，但是覺得還有一些地方可以繼續深挖：1.堆和敗者樹到底 哪一個更優？可以通過理論分析，也可以通過實驗來比較。也許會有人覺得這個很無聊；2.有 沒有近似的算法或者概率算法來解決這個問題？我對這方面實在不熟悉，如果有人有想法的話可 以一塊交流。如果有分析錯誤或遺漏的地方，請告知，我不怕丟人，呵呵！最后請時刻謹記，時 間復雜度不等