求TopN熱搜關鍵詞[大數(shù)據(jù)算法]

搜索引擎的熱門搜索排行榜功能你用過嗎?你知道這個功能是如何實現(xiàn)的嗎?實際上，它的實現(xiàn)并不復雜。搜索引擎每天會接收大量的用戶搜索請求，它會把這些用戶輸入的搜索關鍵詞記錄下來，然后再離線地統(tǒng)計分析，得到最熱門的 Top 10 搜索關鍵詞。

那請你思考下，假設現(xiàn)在我們有一個包含 10 億個搜索關鍵詞的日志文件，如何能快速獲取到熱門榜 Top 10 的搜索關鍵詞呢?

這個問題就可以用堆來解決，這也是堆這種數(shù)據(jù)結構一個非常典型的應用。上一節(jié)我們講了堆和堆排序的一些理論知識，今天我們就來講一講，堆這種數(shù)據(jù)結構幾個非常重要的應用：優(yōu)先級隊列、求 Top K 和求中位數(shù)?！就扑]了解：大數(shù)據(jù)培訓課程】

堆的應用一：優(yōu)先級隊列

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

優(yōu)先級隊列，顧名思義，它首先應該是一個隊列。我們前面講過，隊列最大的特性就是先進先出。不過，在優(yōu)先級隊列中，數(shù)據(jù)的出隊順序不是先進先出，而是按照優(yōu)先級來，優(yōu)先級最高的，最先出隊。

如何實現(xiàn)一個優(yōu)先級隊列呢?方法有很多，但是用堆來實現(xiàn)是最直接、最高效的。這是因為，堆和優(yōu)先級隊列非常相似。一個堆就可以看作一個優(yōu)先級隊列。很多時候，它們只是概念上的區(qū)分而已。往優(yōu)先級隊列中插入一個元素，就相當于往堆中插入一個元素;從優(yōu)先級隊列中取出優(yōu)先級最高的元素，就相當于取出堆頂元素。

你可別小看這個優(yōu)先級隊列，它的應用場景非常多。我們后面要講的很多數(shù)據(jù)結構和算法都要依賴它。比如，赫夫曼編碼、圖的最短路徑、最小生成樹算法等等。不僅如此，很多語言中，都提供了優(yōu)先級隊列的實現(xiàn)，比如，Java 的 PriorityQueue，C++ 的 priority_queue 等。

只講這些應用場景比較空泛，現(xiàn)在，我舉兩個具體的例子，讓你感受一下優(yōu)先級隊列具體是怎么用的。

1. 合并有序小文件

假設我們有 100 個小文件，每個文件的大小是 100MB，每個文件中存儲的都是有序的字符串。我們希望將這些 100 個小文件合并成一個有序的大文件。這里就會用到優(yōu)先級隊列。

整體思路有點像歸并排序中的合并函數(shù)。我們從這 100 個文件中，各取第一個字符串，放入數(shù)組中，然后比較大小，把最小的那個字符串放入合并后的大文件中，并從數(shù)組中刪除。

假設，這個最小的字符串來自于 13.txt 這個小文件，我們就再從這個小文件取下一個字符串，并且放到數(shù)組中，重新比較大小，并且選擇最小的放入合并后的大文件，并且將它從數(shù)組中刪除。依次類推，直到所有的文件中的數(shù)據(jù)都放入到大文件為止。

這里我們用數(shù)組這種數(shù)據(jù)結構，來存儲從小文件中取出來的字符串。每次從數(shù)組中取最小字符串，都需要循環(huán)遍歷整個數(shù)組，顯然，這不是很高效。有沒有更加高效方法呢?

這里就可以用到優(yōu)先級隊列，也可以說是堆。我們將從小文件中取出來的字符串放入到小頂堆中，那堆頂?shù)脑?，也就是?yōu)先級隊列隊首的元素，就是最小的字符串。我們將這個字符串放入到大文件中，并將其從堆中刪除。然后再從小文件中取出下一個字符串，放入到堆中。循環(huán)這個過程，就可以將 100 個小文件中的數(shù)據(jù)依次放入到大文件中。

我們知道，刪除堆頂數(shù)據(jù)和往堆中插入數(shù)據(jù)的時間復雜度都是 O(logn)，n 表示堆中的數(shù)據(jù)個數(shù)，這里就是 100。是不是比原來數(shù)組存儲的方式高效了很多呢?

2. 高性能定時器

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

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

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

這樣，定時器就不需要每隔 1 秒就掃描一遍任務列表了。它拿隊首任務的執(zhí)行時間點，與當前時間點相減，得到一個時間間隔 T。

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

當 T 秒時間過去之后，定時器取優(yōu)先級隊列中隊首的任務執(zhí)行。然后再計算新的隊首任務的執(zhí)行時間點與當前時間點的差值，把這個值作為定時器執(zhí)行下一個任務需要等待的時間。

這樣，定時器既不用間隔 1 秒就輪詢一次，也不用遍歷整個任務列表，性能也就提高了。

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

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

我把這種求 Top K 的問題抽象成兩類。一類是針對靜態(tài)數(shù)據(jù)集合，也就是說數(shù)據(jù)集合事先確定，不會再變。另一類是針對動態(tài)數(shù)據(jù)集合，也就是說數(shù)據(jù)集合事先并不確定，有數(shù)據(jù)動態(tài)地加入到集合中。

針對靜態(tài)數(shù)據(jù)，如何在一個包含 n 個數(shù)據(jù)的數(shù)組中，查找前 K 大數(shù)據(jù)呢?我們可以維護一個大小為 K 的小頂堆，順序遍歷數(shù)組，從數(shù)組中取出取數(shù)據(jù)與堆頂元素比較。如果比堆頂元素大，我們就把堆頂元素刪除，并且將這個元素插入到堆中;如果比堆頂元素小，則不做處理，繼續(xù)遍歷數(shù)組。這樣等數(shù)組中的數(shù)據(jù)都遍歷完之后，堆中的數(shù)據(jù)就是前 K 大數(shù)據(jù)了。

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

針對動態(tài)數(shù)據(jù)求得 Top K 就是實時 Top K。怎么理解呢?我舉一個例子。一個數(shù)據(jù)集合中有兩個操作，一個是添加數(shù)據(jù)，另一個詢問當前的前 K 大數(shù)據(jù)。

如果每次詢問前 K 大數(shù)據(jù)，我們都基于當前的數(shù)據(jù)重新計算的話，那時間復雜度就是 O(nlogK)，n 表示當前的數(shù)據(jù)的大小。實際上，我們可以一直都維護一個 K 大小的小頂堆，當有數(shù)據(jù)被添加到集合中時，我們就拿它與堆頂?shù)脑貙Ρ?。如果比堆頂元素大，我們就把堆頂元素刪除，并且將這個元素插入到堆中;如果比堆頂元素小，則不做處理。這樣，無論任何時候需要查詢當前的前 K 大數(shù)據(jù)，我們都可以里立刻返回給他。

堆的應用三：利用堆求中位數(shù)

前面我們講了如何求 Top K 的問題，現(xiàn)在我們來講下，如何求動態(tài)數(shù)據(jù)集合中的中位數(shù)。

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

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

借助堆這種數(shù)據(jù)結構，我們不用排序，就可以非常高效地實現(xiàn)求中位數(shù)操作。我們來看看，它是如何做到的?

我們需要維護兩個堆，一個大頂堆，一個小頂堆。大頂堆中存儲前半部分數(shù)據(jù)，小頂堆中存儲后半部分數(shù)據(jù)，且小頂堆中的數(shù)據(jù)都大于大頂堆中的數(shù)據(jù)。

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

我們前面也提到，數(shù)據(jù)是動態(tài)變化的，當新添加一個數(shù)據(jù)的時候，我們如何調整兩個堆，讓大頂堆中的堆頂元素繼續(xù)是中位數(shù)呢?

如果新加入的數(shù)據(jù)小于等于大頂堆的堆頂元素，我們就將這個新數(shù)據(jù)插入到大頂堆;如果新加入的數(shù)據(jù)大于等于小頂堆的堆頂元素，我們就將這個新數(shù)據(jù)插入到小頂堆。

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

于是，我們就可以利用兩個堆，一個大頂堆、一個小頂堆，實現(xiàn)在動態(tài)數(shù)據(jù)集合中求中位數(shù)的操作。插入數(shù)據(jù)因為需要涉及堆化，所以時間復雜度變成了 O(logn)，但是求中位數(shù)我們只需要返回大頂堆的堆頂元素就可以了，所以時間復雜度就是 O(1)。

實際上，利用兩個堆不僅可以快速求出中位數(shù)，還可以快速求其他百分位的數(shù)據(jù)，原理是類似的。還記得我們在“為什么要學習數(shù)據(jù)結構與算法”里的這個問題嗎?“如何快速求接口的 99% 響應時間?”我們現(xiàn)在就來看下，利用兩個堆如何來實現(xiàn)。

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

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

如果你還是不太理解，我再舉個例子。假設有 100 個數(shù)據(jù)，分別是 1，2，3，……，100，那 99 百分位數(shù)就是 99，因為小于等于 99 的數(shù)占總個數(shù)的 99%。

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

我們總結一下，如果有 n 個數(shù)據(jù)，將數(shù)據(jù)從小到大排列之后，99 百分位數(shù)大約就是第 n*99% 個數(shù)據(jù)，同類，80 百分位數(shù)大約就是第 n*80% 個數(shù)據(jù)。

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

我們維護兩個堆，一個大頂堆，一個小頂堆。假設當前總數(shù)據(jù)的個數(shù)是 n，大頂堆中保存 n*99% 個數(shù)據(jù)，小頂堆中保存 n*1% 個數(shù)據(jù)。大頂堆堆頂?shù)臄?shù)據(jù)就是我們要找的 99% 響應時間。

每次插入一個數(shù)據(jù)的時候，我們要判斷這個數(shù)據(jù)跟大頂堆和小頂堆堆頂數(shù)據(jù)的大小關系，然后決定插入到哪個堆中。如果這個新插入的數(shù)據(jù)比大頂堆的堆頂數(shù)據(jù)小，那就插入大頂堆;如果這個新插入的數(shù)據(jù)比小頂堆的堆頂數(shù)據(jù)大，那就插入小頂堆。

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

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

解答開篇

學懂了上面的一些應用場景的處理思路，我想你應該能解決開篇的那個問題了吧。假設現(xiàn)在我們有一個包含 10 億個搜索關鍵詞的日志文件，如何快速獲取到 Top 10 最熱門的搜索關鍵詞呢?

處理這個問題，有很多高級的解決方法，比如使用 MapReduce 等。但是，如果我們將處理的場景限定為單機，可以使用的內存為 1GB。那這個問題該如何解決呢?

因為用戶搜索的關鍵詞，有很多可能都是重復的，所以我們首先要統(tǒng)計每個搜索關鍵詞出現(xiàn)的頻率。我們可以通過散列表、平衡二叉查找樹或者其他一些支持快速查找、插入的數(shù)據(jù)結構，來記錄關鍵詞及其出現(xiàn)的次數(shù)。

假設我們選用散列表。我們就順序掃描這 10 億個搜索關鍵詞。當掃描到某個關鍵詞時，我們去散列表中查詢。如果存在，我們就將對應的次數(shù)加一;如果不存在，我們就將它插入到散列表，并記錄次數(shù)為 1。以此類推，等遍歷完這 10 億個搜索關鍵詞之后，散列表中就存儲了不重復的搜索關鍵詞以及出現(xiàn)的次數(shù)。

然后，我們再根據(jù)前面講的用堆求 Top K 的方法，建立一個大小為 10 的小頂堆，遍歷散列表，依次取出每個搜索關鍵詞及對應出現(xiàn)的次數(shù)，然后與堆頂?shù)乃阉麝P鍵詞對比。如果出現(xiàn)次數(shù)比堆頂搜索關鍵詞的次數(shù)多，那就刪除堆頂?shù)年P鍵詞，將這個出現(xiàn)次數(shù)更多的關鍵詞加入到堆中。

以此類推，當遍歷完整個散列表中的搜索關鍵詞之后，堆中的搜索關鍵詞就是出現(xiàn)次數(shù)最多的 Top 10 搜索關鍵詞了。

不知道你發(fā)現(xiàn)了沒有，上面的解決思路其實存在漏洞。10 億的關鍵詞還是很多的。我們假設 10 億條搜索關鍵詞中不重復的有 1 億條，如果每個搜索關鍵詞的平均長度是 50 個字節(jié)，那存儲 1 億個關鍵詞起碼需要 5GB 的內存空間，而散列表因為要避免頻繁沖突，不會選擇太大的裝載因子，所以消耗的內存空間就更多了。而我們的機器只有 1GB 的可用內存空間，所以我們無法一次性將所有的搜索關鍵詞加入到內存中。這個時候該怎么辦呢?

我們在哈希算法那一節(jié)講過，相同數(shù)據(jù)經(jīng)過哈希算法得到的哈希值是一樣的。我們可以哈希算法的這個特點，將 10 億條搜索關鍵詞先通過哈希算法分片到 10 個文件中。

具體可以這樣做：我們創(chuàng)建 10 個空文件 00，01，02，……，09。我們遍歷這 10 億個關鍵詞，并且通過某個哈希算法對其求哈希值，然后哈希值同 10 取模，得到的結果就是這個搜索關鍵詞應該被分到的文件編號。

對這 10 億個關鍵詞分片之后，每個文件都只有 1 億的關鍵詞，去除掉重復的，可能就只有 1000 萬個，每個關鍵詞平均 50 個字節(jié)，所以總的大小就是 500MB。1GB 的內存完全可以放得下。

我們針對每個包含 1 億條搜索關鍵詞的文件，利用散列表和堆，分別求出 Top 10，然后把這個 10 個 Top 10 放在一塊，然后取這 100 個關鍵詞中，出現(xiàn)次數(shù)最多的 10 個關鍵詞，這就是這 10 億數(shù)據(jù)中的 Top 10 最頻繁的搜索關鍵詞了。

內容小結

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

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