Java 堆排序工具類：解決 Top K 問題 (泛型實現)

適用場景

海量數據中尋找最小的 K 個元素 (Top K 最小值)，如日誌分析、推薦系統候選集截斷。時間復雜度 O(n log k)，空間 O(k)，優於全量排序 O(n log n)。

核心代碼 (Java 8+)

import java.util.ArrayList;
import java.util.List;

public final class HeapSort {

    private HeapSort() {} // 工具類

    /**
     * 返回列表中最小的 k 個元素 (無序)
     * @param list 輸入列表 (元素需實現 Comparable)
     * @param k 目標數量
     * @return 大小為 k 的列表
     * @throws IllegalArgumentException k <= 0 或 list.size() < k
     */
    public static > List topKMin(List list, int k) {
        if (k <= 0) throw new IllegalArgumentException("k must be > 0");
        if (list.size() < k) throw new IllegalArgumentException("list size < k");

        // 1. 取前 k 個構建大頂堆 (堆頂為當前 k 個中最大)
        List heap = new ArrayList<>(list.subList(0, k));
        buildMaxHeap(heap);

        // 2. 遍歷剩餘元素，小於堆頂則替換並下沉
        for (int i = k; i < list.size(); i++) {
            T curr = list.get(i);
            if (curr.compareTo(heap.get(0)) < 0) {
                heap.set(0, curr);
                maxHeapify(heap, k, 0);
            }
        }
        return heap;
    }

    // 構建大頂堆 (自下而上)
    private static > void buildMaxHeap(List heap) {
        int n = heap.size();
        for (int i = n / 2 - 1; i >= 0; i--)
            maxHeapify(heap, n, i);
    }

    // 節點 i 下沉維護大頂堆性質
    private static > void maxHeapify(List heap, int n, int i) {
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;

        if (left < n && heap.get(left).compareTo(heap.get(largest)) > 0)
            largest = left;
        if (right < n && heap.get(right).compareTo(heap.get(largest)) > 0)
            largest = right;

        if (largest != i) {
            T tmp = heap.get(i);
            heap.set(i, heap.get(largest));
            heap.set(largest, tmp);
            maxHeapify(heap, n, largest);
        }
    }
}

使用示例

List data = Arrays.asList(9, 3, 5, 1, 7, 2, 8, 4, 6, 0);
List min3 = HeapSort.topKMin(data, 3);
// min3 可能為 [2, 0, 1] (無序，但均為最小 3 個)
min3.sort(Integer::compareTo); // [0, 1, 2]

擴展：Top K 最大值

構建小頂堆，比較邏輯取反 (curr.compareTo(heap.get(0)) > 0) 即可。

注意事項

• 輸入列表不被修改。
• 返回列表內部順序無意義 (堆結構)，如需有序請自行排序。
• 元素類型必須實現 Comparable，或傳入 Comparator 重載版本。