2.1 海底撈幾根針

情境如下:

給定一個數列, 其中有極大量的資料(假設1bilion up好了), 請想一個好方法取出其中的前N名大的資料.

限制: 不可以用分散式系統, 只能在本機處理.

解法:

首先迭代整個數列, 在每一次的迭代中, 用min heap存入當次迭代的資料, 若此時的minheap大小已經達到N+1, 就淘汰樹根後再次做minheapify. 最後, 迭代完所有資料後, 一樣先做minheapify, 然後把樹根砍掉, 因為這時候的樹根會是第N+1筆大的資料, 並不在我們要的解集合中, 完成後, 這時候的min heap大小就是N了, 而這N個資料拿去做heap sort就是結果了.

關於Heap的觀念與操作, 可以看這篇筆記.