Java解決TopK問題

在處理大量資料的時候， 有時候往往需要找出Top前幾的資料， 這時候如果直接對資料進行排序， 在處理海量資料的時候往往就是不可行的了， 而且在排序最好的時間複雜度為nlogn， 當n遠大於需要獲取到的資料的時候， 時間複雜度就顯得過高。 使用最小堆或者最大堆可以很好地解決Top大問題或者Top小問題。

Top大問題解決思路：使用一個固定大小的最小堆， 當堆滿後， 每次添加資料的時候與堆頂元素比較， 若小於堆頂元素， 則捨棄， 若大於堆頂元素， 則刪除堆頂元素， 添加新增元素， 對堆進行重新排序。 Top小問題解決思路：使用一個固定大小的最大堆， 當堆滿後， 每次添加資料到時候與堆頂元素進行比較， 若大於堆頂元素， 則捨棄， 若小於堆頂元素， 則刪除堆頂元素， 添加新增元素， 對堆進行重新排序。

對於n個數， 取Top m個數， 時間複雜度為O(nlogm)， 這樣在n較大情況下， 是優於nlogn的時間複雜度的。

比如10000個資料， 取前100大的數， 那麼時間複雜度就是O(10000log100)。 因為在插入資料的時候需要遍歷元素時間複雜度達到了O(10000)， 然後每次插入過程中進行調整的複雜度為O(log100)， 所以總體時間複雜度為O(10000log100)。

使用Java類庫集合實現

Java集合中的PriorityQueue就可以實現最大堆或者最小堆， 從名字可以知道該集合是優先佇列， 資料結構中的優先佇列就是使用堆來實現的。

// 底層通過一個Object類型資料保存元素 transient Object queue; // 通過Comparator制定比較方法 private final Comparator comparator; // 其中一個構造函數 public PriorityQueue(int initialCapacity, Comparator comparator) { // Note: This restriction of at least one is not actually needed, // but continues for 1.5 compatibility if (initialCapacity

下面就使用PriorityQueue來實現最小堆和最大堆。

在構造PriorityQueue的時候需要傳入一個size和一個比較函數， 制定堆中元素比較規則。 重寫compare(o1, o2)方法， 最小堆使用o1 - o2， 最大堆使用o2 - o1。 public class TopK { private PriorityQueue queue; private int maxSize; //堆的最大容量 public TopK(int maxSize) { if (maxSize (maxSize, new Comparator { @Override public int compare(E o1, E o2) { // 最大堆用o2 - o1， 最小堆用o1 - o2 return (o1.compareTo(o2)); } }); } public void add(E e) { if (queue.size 0) { queue.poll; queue.add(e); } } } public List sortedList { List list = new ArrayList<>(queue); Collections.sort(list); return list; } public static void main(String[] args) { int array = {4, 5, 1, 6, 2, 7, 3, 8}; TopK pq = new TopK(4); for (int n : array) { pq.add(n); } System.out.println(pq.sortedList); } }

運行結果：

使用Java實現

通過上述講述， 基本瞭解最大堆和最小堆情況以及它們與TopK問題的關係， 上面是使用集合實現， 下面使用Java來實現最小堆， 並解決TopK大問題。

限定數據大小。 若堆滿， 則插入過程中與堆頂元素比較， 並做相應操作。 每次刪除堆頂元素後堆做一次調整， 保證最小堆特性。 public class TopK { int items; int currentSize = 0; // 初始化為size + 1， 從下標1開始保存元素。 public TopK(int size) { items = new int[size + 1]; } // 插入元素 public void insert(int x) { if (currentSize == items.length - 1) { if (compare(x, items[1]) 0) { deleteMin; } } int hole = ++currentSize; for (items[0] = x; compare(x, items[hole / 2]) b) { return 1; } return 0; } public static void main(String[] args) { TopK topK = new TopK(10); for (int i = 1; i