Java 数据结构篇-实现堆的核心方法与堆的应用（实现 TOP-K 问题：最小 k 个数）

public class MinHeap<T extends Comparable<T>> {
    private ArrayList<T> list;
 
    public MinHeap() {
        list = new ArrayList<>();
    }
 
    // 向堆中插入元素
    public void insert(T element) {
        list.add(element);
        siftUp(list.size() - 1);
    }
 
    // 从堆中取出最小元素
    public T extractMin() {
        if (list.isEmpty()) return null;
        T min = list.get(0);
        list.set(0, list.get(list.size() - 1));
        list.remove(list.size() - 1);
        siftDown(0);
        return min;
    }
 
    // 获取堆顶元素但不移除它
    public T getMin() {
        if (list.isEmpty()) return null;
        return list.get(0);
    }
 
    // 调整元素以满足堆的性质，向上调整
    private void siftUp(int index) {
        while (index > 0) {
            int parent = (index - 1) / 2;
            if (list.get(parent).compareTo(list.get(index)) <= 0) break;
            Collections.swap(list, parent, index);
            index = parent;
        }
    }
 
    // 调整元素以满足堆的性质，向下调整
    private void siftDown(int index) {
        int half = list.size() / 2;
        while (index < half) {
            // 找到子节点中较小的一个
            int child = (index * 2) + 1;
            if (child + 1 < list.size() && list.get(child + 1).compareTo(list.get(child)) < 0)
                child++;
            if (list.get(index).compareTo(list.get(child)) <= 0) break;
            Collections.swap(list, index, child);
            index = child;
        }
    }
 
    // 获取堆中元素的数量
    public int size() {
        return list.size();
    }
 
    // 判断堆是否为空
    public boolean isEmpty() {
        return list.isEmpty();
    }
 
    // 主函数，用于测试堆的创建和使用
    public static void main(String[] args) {
        MinHeap<Integer> minHeap = new MinHeap<>();
        int[] data = {10, 5, 15, 8, 20, 6};
 
        // 插入元素到堆中
        for (int num : data) {
            minHeap.insert(num);
        }
 
        // 获取最小的k个数
        int k = 3;
        for (int i = 0; i < k; i++) {
            System.out.println(minHeap.extractMin());
        }
    }
}

这段代码实现了一个最小堆，并展示了如何使用它来解决 TOP-K 问题。在主函数中，我们创建了一个最小堆并插入了一些数据，然后连续提取最小的 k 个数。这个过程模拟了堆的应用场景，对于学习数据结构和算法的学生来说具有很好的教育价值。