45節(jié)介紹了堆的概念和算法，上節(jié)介紹了Java中堆的實現(xiàn)類PriorityQueue，PriorityQueue除了用作優(yōu)先級隊列，還可以用來解決一些別的問題，45節(jié)提到了如下兩個應用：

  • 求前K個最大的元素，元素個數(shù)不確定，數(shù)據(jù)量可能很大，甚至源源不斷到來，但需要知道到目前為止的最大的前K個元素。這個問題的變體有：求前K個最小的元素，求第K個最大的，求第K個最小的。
  • 求中值元素，中值不是平均值，而是排序后中間那個元素的值，同樣，數(shù)據(jù)量可能很大，甚至源源不斷到來。 

本節(jié)，我們就來探討如何解決這兩個問題。

求前K個最大的元素

基本思路

一個簡單的思路是排序，排序后取最大的K個就可以了，排序可以使用Arrays.sort()方法，效率為O(N*log2(N))。不過，如果K很小，比如是1，就是取最大值，對所有元素完全排序是毫無必要的。

另一個簡單的思路是選擇，循環(huán)選擇K次，每次從剩下的元素中選擇最大值，這個效率為O(N*K)，如果K的值大于log2(N)，這個就不如完全排序了。

不過，這兩個思路都假定所有元素都是已知的，而不是動態(tài)添加的。如果元素個數(shù)不確定，且源源不斷到來呢？

一個基本的思路是維護一個長度為K的數(shù)組，最前面的K個元素就是目前最大的K個元素，以后每