???在大規(guī)模數(shù)據(jù)處理中，經(jīng)常會(huì)遇到的一類問題：在海量數(shù)據(jù)中找出出現(xiàn)頻率最高的前k個(gè)數(shù)亲轨，或者從海量數(shù)據(jù)中找出最大的前k個(gè)數(shù)趋惨，這類問題通常被稱為top K問題。例如瓶埋，在搜索引擎中希柿，統(tǒng)計(jì)搜索最熱門的10個(gè)查詢?cè)~诊沪；在歌曲庫中統(tǒng)計(jì)下載最高的前10首歌等养筒。
eg：有1億個(gè)浮點(diǎn)數(shù)，如果找出期中最大的10000個(gè)端姚？
該題目解法有很多晕粪，以下逐個(gè)闡述
???最容易想到的方法是將數(shù)據(jù)全部排序，然后在排序后的集合中進(jìn)行查找渐裸，最快的排序算法的時(shí)間復(fù)雜度一般為O（nlogn）巫湘，如快速排序装悲。但是在32位的機(jī)器上，每個(gè)float類型占4個(gè)字節(jié)尚氛，1億個(gè)浮點(diǎn)數(shù)就要占用400MB的存儲(chǔ)空間诀诊，對(duì)于一些可用內(nèi)存小于400M的計(jì)算機(jī)而言，很顯然是不能一次將全部數(shù)據(jù)讀入內(nèi)存進(jìn)行排序的阅嘶。其實(shí)即使內(nèi)存能夠滿足要求（我機(jī)器內(nèi)存都是8GB）属瓣，該方法也并不高效，因?yàn)轭}目的目的是尋找出最大的10000個(gè)數(shù)即可讯柔，而排序卻是將所有的元素都排序了抡蛙，做了很多的無用功。
???第二種方法為局部淘汰法魂迄，該方法與排序方法類似粗截，用一個(gè)容器保存前10000個(gè)數(shù)，然后將剩余的所有數(shù)字——與容器內(nèi)的最小數(shù)字相比捣炬，如果所有后續(xù)的元素都比容器內(nèi)的10000個(gè)數(shù)還小熊昌，那么容器內(nèi)這個(gè)10000個(gè)數(shù)就是最大10000個(gè)數(shù)。如果某一后續(xù)元素比容器內(nèi)最小數(shù)字大遥金，則刪掉容器內(nèi)最小元素浴捆，并將該元素插入容器，最后遍歷完這1億個(gè)數(shù)稿械，得到的結(jié)果容器中保存的數(shù)即為最終結(jié)果了选泻。此時(shí)的時(shí)間復(fù)雜度為O（n+m^2），其中m為容器的大小美莫，即10000页眯。
???第三種方法是分治法，將1億個(gè)數(shù)據(jù)分成100份厢呵，每份100萬個(gè)數(shù)據(jù)窝撵，找到每份數(shù)據(jù)中最大的10000個(gè)，最后在剩下的100X10000個(gè)數(shù)據(jù)里面找出最大的10000個(gè)襟铭。如果100萬數(shù)據(jù)選擇足夠理想碌奉，那么可以過濾掉1億數(shù)據(jù)里面99%的數(shù)據(jù)。100萬個(gè)數(shù)據(jù)里面查找最大的10000個(gè)數(shù)據(jù)的方法如下：用快速排序的方法寒砖，將數(shù)據(jù)分為2堆赐劣，如果大的那堆個(gè)數(shù)N大于10000個(gè)，繼續(xù)對(duì)大堆快速排序一次分成2堆哩都，如果大的那堆個(gè)數(shù)N大于10000個(gè)魁兼，繼續(xù)對(duì)大堆快速排序一次分成2堆，如果大堆個(gè)數(shù)N小于10000個(gè)漠嵌，就在小的那堆里面快速排序一次咐汞，找第10000-n大的數(shù)字盖呼；遞歸以上過程，就可以找到第1w大的數(shù)化撕。參考上面的找出第1w大數(shù)字几晤，就可以類似的方法找到前10000大數(shù)字了。此種方法需要每次的內(nèi)存空間為10^6*4=4MB植阴，一共需要101次這樣的比較锌仅。
???第四種方法是Hash法。如果這1億個(gè)書里面有很多重復(fù)的數(shù)墙贱，先通過Hash法热芹，把這1億個(gè)數(shù)字去重復(fù)，這樣如果重復(fù)率很高的話惨撇，會(huì)減少很大的內(nèi)存用量伊脓，從而縮小運(yùn)算空間，然后通過分治法或最小堆法查找最大的10000個(gè)數(shù)魁衙。
???第五種方法采用小頂堆报腔。首先讀入前10000個(gè)數(shù)來創(chuàng)建大小為10000的最小堆，建堆的時(shí)間復(fù)雜度為O（mlogm）（m為數(shù)組的大小即為10000）剖淀，然后遍歷后續(xù)的數(shù)字纯蛾，并于堆頂（最小）數(shù)字進(jìn)行比較纵隔。如果比最小的數(shù)小翻诉，則繼續(xù)讀取后續(xù)數(shù)字；如果比堆頂數(shù)字大捌刮，則替換堆頂元素并重新調(diào)整堆為最小堆碰煌。整個(gè)過程直至1億個(gè)數(shù)全部遍歷完為止。然后按照中序遍歷的方式輸出當(dāng)前堆中的所有10000個(gè)數(shù)字绅作。該算法的時(shí)間復(fù)雜度為O（nmlogm）芦圾，空間復(fù)雜度是10000（常數(shù)）。
小頂堆可以參照前面的堆排序俄认，解決top k問題是堆排序算法的一種延伸个少。
對(duì)于該種算法，假設(shè)一共是n個(gè)數(shù)眯杏，找前m個(gè)大的夜焦。第一次建堆并調(diào)整的時(shí)間大約為mlog(m)，那么對(duì)于剩下的每個(gè)元素役拴，最壞的情況下就是每個(gè)都調(diào)整堆糊探，堆調(diào)整一次的時(shí)間復(fù)雜度為log(m)钾埂，所以總的時(shí)間復(fù)雜度為（n-m）log(m) + mlog(m) = nlog(m)
小頂堆的方法是最直觀的解決top k問題的方法河闰，還有一種更為高效的方法：Quick Select算法科平。
最直觀：小頂堆（大頂堆 -> 最小100個(gè)數(shù)）；
較高效：Quick Select算法姜性。
Quick Select脫胎于快速排序（Quick Sort）瞪慧，兩個(gè)算法的作者都是Hoare，并且思想也非常接近：選取一個(gè)基準(zhǔn)元素pivot部念，將數(shù)組切分（partition）為兩個(gè)子數(shù)組弃酌，比pivot大的扔左子數(shù)組，比pivot小的扔右子數(shù)組儡炼，然后遞推地切分子數(shù)組妓湘。Quick Select不同于Quick Sort的是其沒有對(duì)每個(gè)子數(shù)組做切分，而是對(duì)目標(biāo)子數(shù)組做切分乌询。其次榜贴，Quick Select與Quick Sort一樣，是一個(gè)不穩(wěn)定的算法妹田；pivot選取直接影響了算法的好壞唬党，worst case下的時(shí)間復(fù)雜度達(dá)到了 O(n2)。
Quick Select的目標(biāo)是找出第k大元素鬼佣，所以
- 若切分后的左子數(shù)組的長(zhǎng)度 > k驶拱，則第k大元素必出現(xiàn)在左子數(shù)組中；
- 若切分后的左子數(shù)組的長(zhǎng)度 = k-1晶衷，則第k大元素為pivot蓝纲；
- 若上述兩個(gè)條件均不滿足，則第k大元素必出現(xiàn)在右子數(shù)組中晌纫。
下面給出Quick Select的Java實(shí)現(xiàn)：
public int findKthLargest(int[] nums, int k) {
return quickSelect(nums, k, 0, nums.length - 1);
}
// quick select to find the kth-largest element
public int quickSelect(int[] arr, int k, int left, int right) {
if (left == right) return arr[right];
int index = partition(arr, left, right);
if (index - left + 1 > k)
return quickSelect(arr, k, left, index - 1);
else if (index - left + 1 == k)
return arr[index];
else
return quickSelect(arr, k - index + left - 1, index + 1, right);
}
上面給出的代碼是求解第k大元素驻龟；若想要得到Top K元素，僅需要將代碼做稍微的修改：比如缸匪，掃描完成后的小頂堆對(duì)應(yīng)于Top K翁狐，Quick Select算法用中間變量保存Top K元素。
