一道java面試題，20億數(shù)字的文本排序，如何取前100？因為這是一個Java問題，所以這是典型的TOPK問題。首先取前100個數(shù)字構建一個最小堆，然后依次從堆的頂部插入剩余的數(shù)字，同時調整堆。堆中最

一道java面試題，20億數(shù)字的文本排序，如何取前100？

因為這是一個Java問題，所以這是典型的TOPK問題。首先取前100個數(shù)字構建一個最小堆，然后依次從堆的頂部插入剩余的數(shù)字，同時調整堆。堆中最后100個元素就是結果。空間復雜度為k，時間復雜度為nlogk

優(yōu)先級隊列也稱為堆。它分為最小堆和最大堆。您提到的最小優(yōu)先級隊列是最小堆。這是一種二叉樹。最小堆的主要特性是每個子樹的根節(jié)點的值小于其子樹的根節(jié)點的值。從堆中獲取最小值并插入一個值并將堆調整為最小值的代價是log2（n）。該算法在時間排序調度算法中有很好的應用。這東西很有用。它通常與其他算法結合使用。例如，我們動態(tài)地給出一些數(shù)字，或者刪除一些數(shù)字，然后詢問當前數(shù)字的中位數(shù)是多少?；蛘邉討B(tài)插入或刪除數(shù)字，并詢問當前數(shù)字的最小值是多少。等待