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

  • 求前K個最大的元素,元素個數(shù)不確定,數(shù)據(jù)量可能很大,甚至源源不斷到來,但需要知道到目前為止的最大的前K個元素。這個問題的變體有:求前K個最小的元素,求第K個最大的,求第K個最小的。

  • 求中值元素,中值不是平均值,而是排序后中間那個元素的值,同樣,數(shù)據(jù)量可能很大,甚至源源不斷到來。 

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

求前K個最大的元素

基本思路

網(wǎng)友評論