45節(jié)介紹了堆的概念和算法，上節(jié)介紹了Java中堆的實(shí)現(xiàn)類PriorityQueue，PriorityQueue除了用作優(yōu)先級(jí)隊(duì)列，還可以用來(lái)解決一些別的問(wèn)題，45節(jié)提到了如下兩個(gè)應(yīng)用：
- 求前K個(gè)最大的元素，元素個(gè)數(shù)不確定，數(shù)據(jù)量可能很大，甚至源源不斷到來(lái)，但需要知道到目前為止的最大的前K個(gè)元素。這個(gè)問(wèn)題的變體有：求前K個(gè)最小的元素，求第K個(gè)最大的，求第K個(gè)最小的。
- 求中值元素，中值不是平均值，而是排序后中間那個(gè)元素的值，同樣，數(shù)據(jù)量可能很大，甚至源源不斷到來(lái)。
本節(jié)，我們就來(lái)探討如何解決這兩個(gè)問(wèn)題。
求前K個(gè)最大的元素
基本思路
一個(gè)簡(jiǎn)單的思路是排序，排序后取最大的K個(gè)就可以了，排序可以使用Arrays.sort()方法，效率為O(N*log2(N))。不過(guò)，如果K很小，比如是1，就是取最大值，對(duì)所有元素完全排序是毫無(wú)必要的。
另一個(gè)簡(jiǎn)單的思路是選擇，循環(huán)選擇K次，每次從剩下的元素中選擇最大值，這個(gè)效率為O(N*K)，如果K的值大于log2(N)，這個(gè)就不如完全排序了。
不過(guò)，這兩個(gè)思路都假定所有元素都是已知的，而不是動(dòng)態(tài)添加的。如果元素個(gè)數(shù)不確定，且源源不斷到來(lái)呢？
一個(gè)基本的思路是維護(hù)一個(gè)長(zhǎng)度為K的數(shù)組，最前面的K個(gè)元素就是目前最大的K個(gè)元素，以后每
