Top K問題在數據分析中非常普遍的一個問題（在面試中也經常被問到），比如：
從20億個數字的文本中，找出最大的前100個。
解決Top K問題有兩種思路，
- 最直觀：小頂堆（大頂堆 -> 最小100個數）；
- 較高效：Quick Select算法。
1. 堆
小頂堆（min-heap）有個重要的性質——每個結點的值均不大於其左右孩子結點的值，則堆頂元素即為整個堆的最小值。JDK中PriorityQueue實現了數據結構堆，通過指定comparator字段來表示小頂堆或大頂堆，默認為null，表示自然序（natural ordering）。
小頂堆解決Top K問題的思路：小頂堆維護當前掃描到的最大100個數，其後每一次的掃描到的元素，若大於堆頂，則入堆，然後刪除堆頂；依此往復，直至掃描完所有元素。Java實現第K大整數代碼如下：
2. Quick Select
Quick Select [1]脫胎於快排（Quick Sort），兩個算法的作者都是Hoare，並且思想也非常接近：選取一個基準元素pivot，將數組切分（partition）為兩個子數組，比pivot大的扔左子數組，比pivot小的扔右子數組，然後遞推地切分子數組。Quick Select不同於Quick Sort的是其沒有對每個子數組做切分，而是對目標子數組做切分。其次，Quick Select與Quick Sort一樣，是一個不穩定的算法；pivot選取直接影響了算法的好壞，worst case下的時間複雜度達到了O(n2)。下面給出Quick Sort的Java實現：
Quick Select的目標是找出第k大元素，所以
- 若切分後的左子數組的長度 > k，則第k大元素必出現在左子數組中；
- 若切分後的左子數組的長度 = k-1，則第k大元素為pivot；
- 若上述兩個條件均不滿足，則第k大元素必出現在右子數組中。
Quick Select的Java實現如下：
上面給出的代碼都是求解第k大元素；若想要得到Top K元素，僅需要將代碼做稍微的修改：比如，掃描完成後的小頂堆對應於Top K，Quick Select算法用中間變量保存Top K元素。
閱讀更多 架構師的修煉之路 的文章
