大資料算法--求TopN熱搜關鍵詞

搜尋引擎的熱門搜尋排行榜功能你用過嗎？你知道這個功能是如何實作的嗎？實際上，它的實作并不複雜。搜尋引擎每天會接收大量的使用者搜尋請求，它會把這些使用者輸入的搜尋關鍵詞記錄下來，然後再離線地統計分析，得到最熱門的 Top 10 搜尋關鍵詞。

那請你思考下，假設現在我們有一個包含 10 億個搜尋關鍵詞的日志檔案，如何能快速擷取到熱門榜 Top 10 的搜尋關鍵詞呢？

這個問題就可以用堆來解決，這也是堆這種資料結構一個非常典型的應用。上一節我們講了堆和堆排序的一些理論知識，今天我們就來講一講，堆這種資料結構幾個非常重要的應用：優先級隊列、求 Top K 和求中位數。

堆的應用一：優先級隊列

首先，我們來看第一個應用場景：優先級隊列。

優先級隊列，顧名思義，它首先應該是一個隊列。我們前面講過，隊列最大的特性就是先進先出。不過，在優先級隊列中，資料的出隊順序不是先進先出，而是按照優先級來，優先級最高的，最先出隊。

如何實作一個優先級隊列呢？方法有很多，但是用堆來實作是最直接、最高效的。這是因為，堆和優先級隊列非常相似。一個堆就可以看作一個優先級隊列。很多時候，它們隻是概念上的區分而已。往優先級隊列中插入一個元素，就相當于往堆中插入一個元素；從優先級隊列中取出優先級最高的元素，就相當于取出堆頂元素。

你可别小看這個優先級隊列，它的應用場景非常多。我們後面要講的很多資料結構和算法都要依賴它。比如，赫夫曼編碼、圖的最短路徑、最小生成樹算法等等。不僅如此，很多語言中，都提供了優先級隊列的實作，比如，Java 的 PriorityQueue，C++ 的 priority_queue 等。

隻講這些應用場景比較空泛，現在，我舉兩個具體的例子，讓你感受一下優先級隊列具體是怎麼用的。

1. 合并有序小檔案

假設我們有 100 個小檔案，每個檔案的大小是 100MB，每個檔案中存儲的都是有序的字元串。我們希望将這些 100 個小檔案合并成一個有序的大檔案。這裡就會用到優先級隊列。

整體思路有點像歸并排序中的合并函數。我們從這 100 個檔案中，各取第一個字元串，放入數組中，然後比較大小，把最小的那個字元串放入合并後的大檔案中，并從數組中删除。

假設，這個最小的字元串來自于 13.txt 這個小檔案，我們就再從這個小檔案取下一個字元串，并且放到數組中，重新比較大小，并且選擇最小的放入合并後的大檔案，并且将它從數組中删除。依次類推，直到所有的檔案中的資料都放入到大檔案為止。

這裡我們用數組這種資料結構，來存儲從小檔案中取出來的字元串。每次從數組中取最小字元串，都需要循環周遊整個數組，顯然，這不是很高效。有沒有更加高效方法呢？

這裡就可以用到優先級隊列，也可以說是堆。我們将從小檔案中取出來的字元串放入到小頂堆中，那堆頂的元素，也就是優先級隊列隊首的元素，就是最小的字元串。我們将這個字元串放入到大檔案中，并将其從堆中删除。然後再從小檔案中取出下一個字元串，放入到堆中。循環這個過程，就可以将 100 個小檔案中的資料依次放入到大檔案中。

我們知道，删除堆頂資料和往堆中插入資料的時間複雜度都是 O(logn)，n 表示堆中的資料個數，這裡就是 100。是不是比原來數組存儲的方式高效了很多呢？

2. 高性能定時器

假設我們有一個定時器，定時器中維護了很多定時任務，每個任務都設定了一個要觸發執行的時間點。定時器每過一個很小的機關時間（比如 1 秒），就掃描一遍任務，看是否有任務到達設定的執行時間。如果到達了，就拿出來執行。

但是，這樣每過 1 秒就掃描一遍任務清單的做法比較低效，主要原因有兩點：第一，任務的約定執行時間離目前時間可能還有很久，這樣前面很多次掃描其實都是徒勞的；第二，每次都要掃描整個任務清單，如果任務清單很大的話，勢必會比較耗時。

針對這些問題，我們就可以用優先級隊列來解決。我們按照任務設定的執行時間，将這些任務存儲在優先級隊列中，隊列首部（也就是小頂堆的堆頂）存儲的是最先執行的任務。

這樣，定時器就不需要每隔 1 秒就掃描一遍任務清單了。它拿隊首任務的執行時間點，與目前時間點相減，得到一個時間間隔 T。

這個時間間隔 T 就是，從目前時間開始，需要等待多久，才會有第一個任務需要被執行。這樣，定時器就可以設定在 T 秒之後，再來執行任務。從目前時間點到（T-1）秒這段時間裡，定時器都不需要做任何事情。

當 T 秒時間過去之後，定時器取優先級隊列中隊首的任務執行。然後再計算新的隊首任務的執行時間點與目前時間點的內插補點，把這個值作為定時器執行下一個任務需要等待的時間。

這樣，定時器既不用間隔 1 秒就輪詢一次，也不用周遊整個任務清單，性能也就提高了。

堆的應用二：利用堆求 Top K

剛剛我們學習了優先級隊列，我們現在來看，堆的另外一個非常重要的應用場景，那就是“求 Top K 問題”。

我把這種求 Top K 的問題抽象成兩類。一類是針對靜态資料集合，也就是說資料集合事先确定，不會再變。另一類是針對動态資料集合，也就是說資料集合事先并不确定，有資料動态地加入到集合中。

針對靜态資料，如何在一個包含 n 個資料的數組中，查找前 K 大資料呢？我們可以維護一個大小為 K 的小頂堆，順序周遊數組，從數組中取出取資料與堆頂元素比較。如果比堆頂元素大，我們就把堆頂元素删除，并且将這個元素插入到堆中；如果比堆頂元素小，則不做處理，繼續周遊數組。這樣等數組中的資料都周遊完之後，堆中的資料就是前 K 大資料了。

周遊數組需要 O(n) 的時間複雜度，一次堆化操作需要 O(logK) 的時間複雜度，是以最壞情況下，n 個元素都入堆一次，是以時間複雜度就是 O(nlogK)。

針對動态資料求得 Top K 就是實時 Top K。怎麼了解呢？我舉一個例子。一個資料集合中有兩個操作，一個是添加資料，另一個詢問目前的前 K 大資料。

如果每次詢問前 K 大資料，我們都基于目前的資料重新計算的話，那時間複雜度就是 O(nlogK)，n 表示目前的資料的大小。實際上，我們可以一直都維護一個 K 大小的小頂堆，當有資料被添加到集合中時，我們就拿它與堆頂的元素對比。如果比堆頂元素大，我們就把堆頂元素删除，并且将這個元素插入到堆中；如果比堆頂元素小，則不做處理。這樣，無論任何時候需要查詢目前的前 K 大資料，我們都可以裡立刻傳回給他。

堆的應用三：利用堆求中位數

前面我們講了如何求 Top K 的問題，現在我們來講下，如何求動态資料集合中的中位數。

中位數，顧名思義，就是處在中間位置的那個數。如果資料的個數是奇數，把資料從小到大排列，那第 n/2+1 個資料就是中位數；如果資料的個數是偶數的話，那處于中間位置的資料有兩個，第n/2 個和第 n/2+1 個資料，這個時候，我們可以随意取一個作為中位數，比如取兩個數中靠前的那個，就是第 n/2 個資料。

對于一組靜态資料，中位數是固定的，我們可以先排序，第 n/2 個資料就是中位數。每次詢問中位數的時候，我們直接傳回這個固定的值就好了。是以，盡管排序的代價比較大，但是邊際成本會很小。但是，如果我們面對的是動态資料集合，中位數在不停地變動，如果再用先排序的方法，每次詢問中位數的時候，都要先進行排序，那效率就不高了。

借助堆這種資料結構，我們不用排序，就可以非常高效地實作求中位數操作。我們來看看，它是如何做到的？

我們需要維護兩個堆，一個大頂堆，一個小頂堆。大頂堆中存儲前半部分資料，小頂堆中存儲後半部分資料，且小頂堆中的資料都大于大頂堆中的資料。

也就是說，如果有 n 個資料，n 是偶數，我們從小到大排序，那前 n/2 個資料存儲在大頂堆中，後 n/2 個資料存儲在小頂堆中。這樣，大頂堆中的堆頂元素就是我們要找的中位數。如果 n 是奇數，情況是類似的，大頂堆就存儲 n/2+1 個資料，小頂堆中就存儲 n/2 個資料。

我們前面也提到，資料是動态變化的，當新添加一個資料的時候，我們如何調整兩個堆，讓大頂堆中的堆頂元素繼續是中位數呢？

如果新加入的資料小于等于大頂堆的堆頂元素，我們就将這個新資料插入到大頂堆；如果新加入的資料大于等于小頂堆的堆頂元素，我們就将這個新資料插入到小頂堆。

這個時候就有可能出現，兩個堆中的資料個數不符合前面約定的情況：如果 n 是偶數，兩個堆中的資料個數都是n/2；如果 n 是奇數，大頂堆有 n/2+1 個資料，小頂堆有 n/2 個資料。這個時候，我們可以從一個堆中不停地将堆頂元素移動到另一個堆，通過這樣的調整，來讓兩個堆中的資料滿足上面的約定。

于是，我們就可以利用兩個堆，一個大頂堆、一個小頂堆，實作在動态資料集合中求中位數的操作。插入資料因為需要涉及堆化，是以時間複雜度變成了 O(logn)，但是求中位數我們隻需要傳回大頂堆的堆頂元素就可以了，是以時間複雜度就是 O(1)。

實際上，利用兩個堆不僅可以快速求出中位數，還可以快速求其他百分位的資料，原理是類似的。還記得我們在“為什麼要學習資料結構與算法”裡的這個問題嗎？“如何快速求接口的 99% 響應時間？”我們現在就來看下，利用兩個堆如何來實作。

在開始這個問題的講解之前，我先解釋一下，什麼是“99% 響應時間”。

中位數的概念就是将資料從小到大排列，處于中間位置，就叫中位數，這個資料會大于等于前面 50% 的資料。99 百分位數的概念可以類比中位數，如果将一組資料從小到大排列，這個 99 百分位數就是大于前面 99% 資料的那個資料。

如果你還是不太了解，我再舉個例子。假設有 100 個資料，分别是 1，2，3，……，100，那 99 百分位數就是 99，因為小于等于 99 的數占總個數的 99%。

弄懂了這個概念，我們再來看 99% 響應時間。如果有 100 個接口通路請求，每個接口請求的響應時間都不同，比如 55 毫秒、100 毫秒、23 毫秒等，我們把這 100 個接口的響應時間按照從小到大排列，排在第 99 的那個資料就是 99% 響應時間，也叫 99 百分位響應時間。

我們總結一下，如果有 n 個資料，将資料從小到大排列之後，99 百分位數大約就是第 n*99% 個資料，同類，80 百分位數大約就是第 n*80% 個資料。

弄懂了這些，我們再來看如何求 99% 響應時間。

我們維護兩個堆，一個大頂堆，一個小頂堆。假設目前總資料的個數是 n，大頂堆中儲存 n*99% 個資料，小頂堆中儲存 n*1% 個資料。大頂堆堆頂的資料就是我們要找的 99% 響應時間。

每次插入一個資料的時候，我們要判斷這個資料跟大頂堆和小頂堆堆頂資料的大小關系，然後決定插入到哪個堆中。如果這個新插入的資料比大頂堆的堆頂資料小，那就插入大頂堆；如果這個新插入的資料比小頂堆的堆頂資料大，那就插入小頂堆。

但是，為了保持大頂堆中的資料占 99%，小頂堆中的資料占 1%，在每次新插入資料之後，我們都要重新計算，這個時候大頂堆和小頂堆中的資料個數，是否還符合 99:1 這個比例。如果不符合，我們就将一個堆中的資料移動到另一個堆，直到滿足這個比例。移動的方法類似前面求中位數的方法，這裡我就不啰嗦了。

通過這樣的方法，每次插入資料，可能會涉及幾個資料的堆化操作，是以時間複雜度是 O(logn)。每次求 99% 響應時間的時候，直接傳回大頂堆中的堆頂資料即可，時間複雜度是 O(1)。

解答開篇

學懂了上面的一些應用場景的處理思路，我想你應該能解決開篇的那個問題了吧。假設現在我們有一個包含 10 億個搜尋關鍵詞的日志檔案，如何快速擷取到 Top 10 最熱門的搜尋關鍵詞呢？

處理這個問題，有很多進階的解決方法，比如使用 MapReduce 等。但是，如果我們将處理的場景限定為單機，可以使用的記憶體為 1GB。那這個問題該如何解決呢？

因為使用者搜尋的關鍵詞，有很多可能都是重複的，是以我們首先要統計每個搜尋關鍵詞出現的頻率。我們可以通過散清單、平衡二叉查找樹或者其他一些支援快速查找、插入的資料結構，來記錄關鍵詞及其出現的次數。

假設我們選用散清單。我們就順序掃描這 10 億個搜尋關鍵詞。當掃描到某個關鍵詞時，我們去散清單中查詢。如果存在，我們就将對應的次數加一；如果不存在，我們就将它插入到散清單，并記錄次數為 1。以此類推，等周遊完這 10 億個搜尋關鍵詞之後，散清單中就存儲了不重複的搜尋關鍵詞以及出現的次數。

然後，我們再根據前面講的用堆求 Top K 的方法，建立一個大小為 10 的小頂堆，周遊散清單，依次取出每個搜尋關鍵詞及對應出現的次數，然後與堆頂的搜尋關鍵詞對比。如果出現次數比堆頂搜尋關鍵詞的次數多，那就删除堆頂的關鍵詞，将這個出現次數更多的關鍵詞加入到堆中。

以此類推，當周遊完整個散清單中的搜尋關鍵詞之後，堆中的搜尋關鍵詞就是出現次數最多的 Top 10 搜尋關鍵詞了。

不知道你發現了沒有，上面的解決思路其實存在漏洞。10 億的關鍵詞還是很多的。我們假設 10 億條搜尋關鍵詞中不重複的有 1 億條，如果每個搜尋關鍵詞的平均長度是 50 個位元組，那存儲 1 億個關鍵詞起碼需要 5GB 的記憶體空間，而散清單因為要避免頻繁沖突，不會選擇太大的裝載因子，是以消耗的記憶體空間就更多了。而我們的機器隻有 1GB 的可用記憶體空間，是以我們無法一次性将所有的搜尋關鍵詞加入到記憶體中。這個時候該怎麼辦呢？

我們在雜湊演算法那一節講過，相同資料經過雜湊演算法得到的哈希值是一樣的。我們可以雜湊演算法的這個特點，将 10 億條搜尋關鍵詞先通過雜湊演算法分片到 10 個檔案中。

具體可以這樣做：我們建立 10 個空檔案 00，01，02，……，09。我們周遊這 10 億個關鍵詞，并且通過某個雜湊演算法對其求哈希值，然後哈希值同 10 取模，得到的結果就是這個搜尋關鍵詞應該被分到的檔案編号。

對這 10 億個關鍵詞分片之後，每個檔案都隻有 1 億的關鍵詞，去除掉重複的，可能就隻有 1000 萬個，每個關鍵詞平均 50 個位元組，是以總的大小就是 500MB。1GB 的記憶體完全可以放得下。

我們針對每個包含 1 億條搜尋關鍵詞的檔案，利用散清單和堆，分别求出 Top 10，然後把這個 10 個 Top 10 放在一塊，然後取這 100 個關鍵詞中，出現次數最多的 10 個關鍵詞，這就是這 10 億資料中的 Top 10 最頻繁的搜尋關鍵詞了。

内容小結

我們今天主要講了堆的幾個重要的應用，它們分别是：優先級隊列、求 Top K 問題和求中位數問題。

優先級隊列是一種特殊的隊列，優先級高的資料先出隊，而不再像普通的隊列那樣，先進先出。實際上，堆就可以看作優先級隊列，隻是稱謂不一樣罷了。求 Top K 問題又可以分為針對靜态資料和針對動态資料，隻需要利用一個堆，就可以做到非常高效率的查詢 Top K 的資料。求中位數實際上還有很多變形，比如求 99 百分位資料、90 百分位資料等，處理的思路都是一樣的，即利用兩個堆，一個大頂堆，一個小頂堆，随着資料的動态添加，動态調整兩個堆中的資料，最後大頂堆的堆頂元素就是要求的資料。