先來聊聊Top K演算法，具體內容如下
應用場景：
搜尋引擎會透過日誌檔案將使用者每次檢索所使用的所有檢索串都記錄下來，每個查詢串的長度為1-255位元組。
假設目前有一千萬個記錄（這些查詢串的重複度比較高，雖然總數是1千萬，但如果除去重複後，不超過3百萬個。一個查詢串的重複度越高，說明查詢它的使用者越多，也就是越熱門。
必備知識：
什麼是雜湊表？
雜湊表（Hash table，也叫散式清單），是根據關鍵碼值(Key value)而直接進行存取的資料結構。
也就是說，它透過將關鍵碼值對應到表中一個位置來存取記錄，以加快尋找的速度。這個映射函數叫做雜湊函數，存放記錄的陣列叫做散列表。
雜湊表的做法其實很簡單，就是把Key透過一個固定的演算法函數既所謂的雜湊函數轉換成一個整數數字，然後就將該數字對數組長度進行取餘，取餘結果就當作數組的下標，將value儲存在以該數字為下標的數組空間。
而當使用哈希表進行查詢的時候，就是再次使用哈希函數將key轉換為對應的數組下標，並定位到該空間獲取value，如此一來，就可以充分利用到數組的定位性能進行數據定位。
問題解析：
要統計最熱門查詢，首先就是要統計每個Query出現的次數，然後根據統計結果，找出Top 10。所以我們可以基於這個思路分兩步驟來設計這個演算法。
即，此問題的解決分為以下兩個步驟：
第一步：Query統計 (統計出每個Query出現的次數)
Query統計有以下兩個方法，可供選擇：
1）、直接排序法 (常在日誌檔案中統計時，使用cat file|format key|sort | uniq -c | sort -nr | head -n 10，就是這個方法)
首先我們最先想到的的演算法就是排序了，先對這個日誌裡面的所有Query都進行排序，然後再遍歷排好序的Query，統計每個Query出現的次數了。
但是題目中有明確要求，那就是內存不能超過1G，一千萬條記錄，每筆記錄是255Byte，很顯然要佔據2.375G內存，這個條件就不滿足要求了。
讓我們回憶一下資料結構課程上的內容，當資料量比較大而且記憶體無法裝下的時候，我們可以採用外排序的方法來進行排序，這裡我們可以採用歸併排序，因為歸併排序有一個比較好的時間複雜度O(NlgN)。
排完序之後我們再對已經有序的Query檔案進行遍歷，統計每個Query出現的次數，再次寫入檔案中。
綜合分析一下，排序的時間複雜度是O(NlgN)，而遍歷的時間複雜度是O(N)，因此該演算法的整體時間複雜度就是O(N+NlgN)=O（NlgN） 。
2）、Hash Table法 (此方法統計字串出現的次數非常好)
在第1個方法中，我們採用了排序的辦法來統計每個Query出現的次數，時間複雜度是NlgN，那麼能不能有更好的方法來存儲，而時間複雜度更低呢？
題目中說明了，雖然有一千萬個Query，但是由於重複度比較高，因此事實上只有300萬的Query，每個Query 255Byte，因此我們可以考慮把他們都放進內存中去，而現在只是需要一個合適的資料結構，在這裡，Hash Table絕對是我們優先的選擇，因為Hash Table的查詢速度非常的快，幾乎是O(1)的時間複雜度。
那麼，我們的演算法就擁有了：
維護一個Key為Query字符串，Value為該Query出現次數的HashTable，每次讀取一個Query，如果該字符串不在Table中，那麼加入該字符串，並且將Value值設為1；如果該字符串在Table中，那麼將該字符串的計數加一即可。最終我們在O(N)的時間複雜度內完成了對此海量資料的處理。
本方法相比演算法1：在時間複雜度上提高了一個數量級，為O（N），但不僅僅是時間複雜度上的優化，該方法只需要IO數據文件一次，而算法1的IO次數較多的，因此此演算法2比演算法1在工程上有更好的可操作性。
第二步：求Top 10(找出出現次數最多的10個)
演算法一：普通排序（我們只用找出top10，所以全部排序有冗餘）
我想對於排序演算法大家都已經不陌生了，這裡不在贅述，我們要注意的是排序演算法的時間複雜度是NlgN，在本題目中，三百萬筆記錄，用1G記憶體是可以存下的。
演算法二：部分排序
題目要求是求出Top 10，因此我們沒有必要對所有的Query都進行排序，我們只需要維護一個10個大小的數組，初始化放入10個Query，按照每個Query的統計次數由大到小排序，然後遍歷這300萬筆記錄，每讀一條記錄就和數組最後一個Query對比，如果小於這個Query，那麼繼續遍歷，否則，將數組中最後一條數據淘汰(還是要放在合適的位置，保持有序)，加入目前的Query。最後當所有的資料都遍歷完畢之後，那麼這個陣列中的10個Query就是我們要找的Top10了。
不難分析出，這樣，演算法的最壞時間複雜度是N*K， 其中K是指top多少。
演算法三：堆
在演算法二中，我們已經將時間複雜度由NlogN優化到N*K，不得不說這是一個比較大的改進了，可是有沒有更好的辦法呢？
分析一下，在演算法二中，每次比較完成之後，所需的操作複雜度都是K，因為要把元素插入到一個線性表之中，而且採用的是順序比較。這裡我們注意一下，該數組是有序的，一次我們每次查找的時候可以採用二分的方法查找，這樣操作的複雜度就降到了logK，可是，隨之而來的問題就是數據移動，因為移動數據次數增加了。不過，這個演算法還是比演算法二有了進步。
基於上述的分析，我們想想，有沒有一種既能快速查找，又能快速移動元素的資料結構呢？
答案是肯定的，那就是堆。
藉助堆疊結構，我們可以在log量級的時間內找到並調整/移動。因此到這裡，我們的演算法可以改進為這樣，維護一個K(該題目中是10)大小的小根堆，然後遍歷300萬的Query，分別和根元素進行比較。
思想與上述演算法二一致，只是在演算法三，我們採用了最小堆這種資料結構來取代數組，把查找目標元素的時間複雜度有O（K）降到了O（logK）。
那麼這樣，採用堆疊資料結構，演算法三，最終的時間複雜度就降到了N*logK，和演算法二相比，又有了比較大的改進。
至此，演算法就完全結束了，經過上述第一步、先用Hash表統計每個Query出現的次數，O（N）；然後第二步、採用堆資料結構找出Top 10，N* O（logK）。所以，我們最終的時間複雜度是：O（N） + N'*O（logK）。 （N為1000萬，N'為300萬）。
js如何使用堆疊實作Top K 演算法?
1. 使用堆疊演算法實作Top，時間複雜度為 O(LogN)
function top(arr,comp){
if(arr.length == 0){return ;}
var i = arr.length / 2 | 0 ;
for(;i >= 0; i--){
if(comp(arr[i], arr[i * 2])){exch(arr, i, i*2);}
if(comp(arr[i], arr[i * 2 + 1])) {exch(arr, i, i*2 + 1);}
}
return arr[0];
}
function exch(arr,i,j){
var t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
登入後複製
2. 呼叫K次堆實現，時間複雜度為 O(K * LogN)
function topK(arr,n,comp){
if(!arr || arr.length == 0 || n <=0 || n > arr.length){
return -1;
}
var ret = new Array();
for(var i = 0;i < n; i++){
var max = top(arr,comp);
ret.push(max);
arr.splice(0,1);
}
return ret;
}登入後複製
3.檢定
var ret = topK(new Array(16,22,91,0,51,44,23),3,function (a,b){return a < b;});
console.log(ret);登入後複製
以上就是為大家分享的使用堆實現Top K演算法，何為Top K演算法，希望對大家的學習有所幫助。
