Top k - 海量資料處理問題

所謂的top k 問題，海量資料找最大的或者最小的前K個資料。

最大的這種問題處理方式：

先進行哈希分割，再将這些資料前K個元素建立一個最小堆，如果之後的元素比堆頂大的話，将堆頂元素替換為該元素，這樣将剩餘的元素依次這樣周遊完，這個堆的所有元素就是最大的前K個元素。

最小的這種問題處理方式：

先進行哈希分割，将這些資料，前K個元素建立一個最大堆，如果其後元素，比堆頂小，用該元素完成替換即可。

（哈希分割，即把一個大檔案分割成M個小檔案，每個大檔案中的資料用直接取餘法%M，最後把得到的哈希位址作為該資料存放的檔案号）

分析：

為什麼最大的前K個元素，要用最小堆呢?

因為，如果一個元素比堆頂小，那麼它肯定比這個最小堆的所有元素小，那它肯定不是前K個最大的之一。這裡把堆頂當一個标準，比它大的才能加入到前K個集合中。

如果這裡我們使用最大堆，那麼該元素比堆頂小，但是它不一定比堆下面的元素小，是以如果我們直接插入是不正确的。那麼如果我們用該元素比堆頂大的話插入，但是這由出問題了，即使該元素被堆頂大可以插入，但出堆的不應該是故堆頂啊，應該是堆内最小的元素。可沒法找到堆内最小元素，因為堆隻保證父與子有序性。是以在找最大的前K個元素的問題中我們使用最小堆。