Top k - 海量数据处理问题

所谓的top k 问题，海量数据找最大的或者最小的前K个数据。

最大的这种问题处理方式：

先进行哈希分割，再将这些数据前K个元素建立一个最小堆，如果之后的元素比堆顶大的话，将堆顶元素替换为该元素，这样将剩余的元素依次这样遍历完，这个堆的所有元素就是最大的前K个元素。

最小的这种问题处理方式：

先进行哈希分割，将这些数据，前K个元素建立一个最大堆，如果其后元素，比堆顶小，用该元素完成替换即可。

（哈希分割，即把一个大文件分割成M个小文件，每个大文件中的数据用直接取余法%M，最后把得到的哈希地址作为该数据存放的文件号）

分析：

为什么最大的前K个元素，要用最小堆呢?

因为，如果一个元素比堆顶小，那么它肯定比这个最小堆的所有元素小，那它肯定不是前K个最大的之一。这里把堆顶当一个标准，比它大的才能加入到前K个集合中。

如果这里我们使用最大堆，那么该元素比堆顶小，但是它不一定比堆下面的元素小，所以如果我们直接插入是不正确的。那么如果我们用该元素比堆顶大的话插入，但是这由出问题了，即使该元素被堆顶大可以插入，但出堆的不应该是故堆顶啊，应该是堆内最小的元素。可没法找到堆内最小元素，因为堆只保证父与子有序性。所以在找最大的前K个元素的问题中我们使用最小堆。