先來聊一聊Top K算法，具體內(nèi)容如下
應(yīng)用場(chǎng)景：
搜索引擎會(huì)通過日志文件把用戶每次檢索使用的所有檢索串都記錄下來，每個(gè)查詢串的長(zhǎng)度為1-255字節(jié)。
假設(shè)目前有一千萬個(gè)記錄（這些查詢串的重復(fù)度比較高，雖然總數(shù)是1千萬，但如果除去重復(fù)后，不超過3百萬個(gè)。一個(gè)查詢串的重復(fù)度越高，說明查詢它的用戶越多，也就是越熱門。），請(qǐng)你統(tǒng)計(jì)最熱門的10個(gè)查詢串，要求使用的內(nèi)存不能超過1G。
必備知識(shí)：
什么是哈希表？
哈希表（Hash table，也叫散列表），是根據(jù)關(guān)鍵碼值(Key value)而直接進(jìn)行訪問的數(shù)據(jù)結(jié)構(gòu)。
也就是說，它通過把關(guān)鍵碼值映射到表中一個(gè)位置來訪問記錄，以加快查找的速度。這個(gè)映射函數(shù)叫做散列函數(shù)，存放記錄的數(shù)組叫做散列表。
哈希表的做法其實(shí)很簡(jiǎn)單，就是把Key通過一個(gè)固定的算法函數(shù)既所謂的哈希函數(shù)轉(zhuǎn)換成一個(gè)整型數(shù)字，然后就將該數(shù)字對(duì)數(shù)組長(zhǎng)度進(jìn)行取余，取余結(jié)果就當(dāng)作數(shù)組的下標(biāo)，將value存儲(chǔ)在以該數(shù)字為下標(biāo)的數(shù)組空間里。
而當(dāng)使用哈希表進(jìn)行查詢的時(shí)候，就是再次使用哈希函數(shù)將key轉(zhuǎn)換為對(duì)應(yīng)的數(shù)組下標(biāo)，并定位到該空間獲取value，如此一來，就可以充分利用到數(shù)組的定位性能進(jìn)行數(shù)據(jù)定位。
問題解析：
要統(tǒng)計(jì)最熱門查詢，首先就是要統(tǒng)計(jì)每個(gè)Query出現(xiàn)的次數(shù)，然后根據(jù)統(tǒng)計(jì)結(jié)果，找出Top 10。所以我們可以基于這個(gè)思路分兩步來設(shè)計(jì)該算法。
即，此問題的解決分為以下倆個(gè)步驟：
第一步：Query統(tǒng)計(jì) (統(tǒng)計(jì)出每個(gè)Query出現(xiàn)的次數(shù))
Query統(tǒng)計(jì)有以下倆個(gè)方法，可供選擇：
1）、直接排序法 (經(jīng)常在日志文件中統(tǒng)計(jì)時(shí)，使用cat file|format key|sort | uniq -c | sort -nr | head -n 10，就是這種方法)
首先我們最先想到的的算法就是排序了，首先對(duì)這個(gè)日志里面的所有Query都進(jìn)行排序，然后再遍歷排好序的Query，統(tǒng)計(jì)每個(gè)Query出現(xiàn)的次數(shù)了。
但是題目中有明確要求，那就是內(nèi)存不能超過1G，一千萬條記錄，每條記錄是255Byte，很顯然要占據(jù)2.375G內(nèi)存，這個(gè)條件就不滿足要求了。
讓我們回憶一下數(shù)據(jù)結(jié)構(gòu)課程上的內(nèi)容，當(dāng)數(shù)據(jù)量比較大而且內(nèi)存無法裝下的時(shí)候，我們可以采用外排序的方法來進(jìn)行排序，這里我們可以采用歸并排序，因?yàn)闅w并排序有一個(gè)比較好的時(shí)間復(fù)雜度O(NlgN)。
排完序之后我們?cè)賹?duì)已經(jīng)有序的Query文件進(jìn)行遍歷，統(tǒng)計(jì)每個(gè)Query出現(xiàn)的次數(shù)，再次寫入文件中。
綜合分析一下，排序的時(shí)間復(fù)雜度是O(NlgN)，而遍歷的時(shí)間復(fù)雜度是O(N)，因此該算法的總體時(shí)間復(fù)雜度就是O(N+NlgN)=O（NlgN）。
2）、Hash Table法 (這種方法統(tǒng)計(jì)字符串出現(xiàn)的次數(shù)非常好)
在第1個(gè)方法中，我們采用了排序的辦法來統(tǒng)計(jì)每個(gè)Query出現(xiàn)的次數(shù)，時(shí)間復(fù)雜度是NlgN，那么能不能有更好的方法來存儲(chǔ)，而時(shí)間復(fù)雜度更低呢？
題目中說明了，雖然有一千萬個(gè)Query，但是由于重復(fù)度比較高，因此事實(shí)上只有300萬的Query，每個(gè)Query 255Byte，因此我們可以考慮把他們都放進(jìn)內(nèi)存中去，而現(xiàn)在只是需要一個(gè)合適的數(shù)據(jù)結(jié)構(gòu)，在這里，Hash Table絕對(duì)是我們優(yōu)先的選擇，因?yàn)镠ash Table的查詢速度非常的快，幾乎是O(1)的時(shí)間復(fù)雜度。
那么，我們的算法就有了：
維護(hù)一個(gè)Key為Query字串，Value為該Query出現(xiàn)次數(shù)的HashTable，每次讀取一個(gè)Query，如果該字串不在Table中，那么加入該字串，并且將Value值設(shè)為1；如果該字串在Table中，那么將該字串的計(jì)數(shù)加一即可。最終我們?cè)贠(N)的時(shí)間復(fù)雜度內(nèi)完成了對(duì)該海量數(shù)據(jù)的處理。
本方法相比算法1：在時(shí)間復(fù)雜度上提高了一個(gè)數(shù)量級(jí)，為O（N），但不僅僅是時(shí)間復(fù)雜度上的優(yōu)化，該方法只需要IO數(shù)據(jù)文件一次，而算法1的IO次數(shù)較多的，因此該算法2比算法1在工程上有更好的可操作性。
第二步：找出Top 10(找出出現(xiàn)次數(shù)最多的10個(gè))
算法一：普通排序（我們只用找出top10，所以全部排序有冗余）
我想對(duì)于排序算法大家都已經(jīng)不陌生了，這里不在贅述，我們要注意的是排序算法的時(shí)間復(fù)雜度是NlgN，在本題目中，三百萬條記錄，用1G內(nèi)存是可以存下的。
算法二：部分排序
題目要求是求出Top 10，因此我們沒有必要對(duì)所有的Query都進(jìn)行排序，我們只需要維護(hù)一個(gè)10個(gè)大小的數(shù)組，初始化放入10個(gè)Query，按照每個(gè)Query的統(tǒng)計(jì)次數(shù)由大到小排序，然后遍歷這300萬條記錄，每讀一條記錄就和數(shù)組最后一個(gè)Query對(duì)比，如果小于這個(gè)Query，那么繼續(xù)遍歷，否則，將數(shù)組中最后一條數(shù)據(jù)淘汰(還是要放在合適的位置，保持有序)，加入當(dāng)前的Query。最后當(dāng)所有的數(shù)據(jù)都遍歷完畢之后，那么這個(gè)數(shù)組中的10個(gè)Query便是我們要找的Top10了。
不難分析出，這樣，算法的最壞時(shí)間復(fù)雜度是N*K， 其中K是指top多少。
算法三：堆
在算法二中，我們已經(jīng)將時(shí)間復(fù)雜度由NlogN優(yōu)化到N*K，不得不說這是一個(gè)比較大的改進(jìn)了，可是有沒有更好的辦法呢？
分析一下，在算法二中，每次比較完成之后，需要的操作復(fù)雜度都是K，因?yàn)橐言夭迦氲揭粋€(gè)線性表之中，而且采用的是順序比較。這里我們注意一下，該數(shù)組是有序的，一次我們每次查找的時(shí)候可以采用二分的方法查找，這樣操作的復(fù)雜度就降到了logK，可是，隨之而來的問題就是數(shù)據(jù)移動(dòng)，因?yàn)橐苿?dòng)數(shù)據(jù)次數(shù)增多了。不過，這個(gè)算法還是比算法二有了改進(jìn)。
基于以上的分析，我們想想，有沒有一種既能快速查找，又能快速移動(dòng)元素的數(shù)據(jù)結(jié)構(gòu)呢？
回答是肯定的，那就是堆。
借助堆結(jié)構(gòu)，我們可以在log量級(jí)的時(shí)間內(nèi)查找和調(diào)整/移動(dòng)。因此到這里，我們的算法可以改進(jìn)為這樣，維護(hù)一個(gè)K(該題目中是10)大小的小根堆，然后遍歷300萬的Query，分別和根元素進(jìn)行對(duì)比。
思想與上述算法二一致，只是在算法三，我們采用了最小堆這種數(shù)據(jù)結(jié)構(gòu)代替數(shù)組，把查找目標(biāo)元素的時(shí)間復(fù)雜度有O（K）降到了O（logK）。
那么這樣，采用堆數(shù)據(jù)結(jié)構(gòu)，算法三，最終的時(shí)間復(fù)雜度就降到了N*logK，和算法二相比，又有了比較大的改進(jìn)。
至此，算法就完全結(jié)束了，經(jīng)過上述第一步、先用Hash表統(tǒng)計(jì)每個(gè)Query出現(xiàn)的次數(shù)，O（N）；然后第二步、采用堆數(shù)據(jù)結(jié)構(gòu)找出Top 10，N*O（logK）。所以，我們最終的時(shí)間復(fù)雜度是：O（N） + N'*O（logK）。（N為1000萬，N'為300萬）。
js如何使用堆實(shí)現(xiàn)Top K 算法?
1. 使用堆算法實(shí)現(xiàn)Top，時(shí)間復(fù)雜度為 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. 調(diào)用K次堆實(shí)現(xiàn)，時(shí)間復(fù)雜度為 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.測(cè)試
var ret = topK(new Array(16,22,91,0,51,44,23),3,function (a,b){return a < b;}); console.log(ret); 以上就是為大家分享的使用堆實(shí)現(xiàn)Top K算法，何為Top K算法，希望對(duì)大家的學(xué)習(xí)有所幫助。
