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

堆的核心方法

堆是一种特殊的树形数据结构，广泛应用于优先队列、图的最短路径算法等。堆有两种类型：最大堆和最小堆。最大堆的每个节点都大于或等于其子节点，最小堆则相反。

在 Java 中，我们可以使用数组来有效地实现堆。下面是一些关键的操作方法：

1. 插入操作：将一个元素插入堆中，之后需要通过上浮操作维护堆的性质。
2. 删除操作：通常删除堆顶元素（最大或最小），将最后一个元素放到堆顶，然后通过下沉操作维护堆的性质。
3. 建堆操作：将一个无序数组转换成堆的形式。

下面是 Java 中的堆实现代码示例：

public class MinHeap {
    private int[] heap;
    private int size; // 当前堆的大小
    private int capacity; // 堆的最大容量

    public MinHeap(int capacity) {
        this.capacity = capacity;
        heap = new int[capacity];
        size = 0;
    }

    // 插入元素
    public void insert(int key) {
        if (size == capacity) {
            throw new IllegalStateException("堆已满");
        }
        heap[size] = key; // 添加新元素
        size++;
        heapifyUp(size - 1); // 维护堆的性质
    }

    // 上浮操作
    private void heapifyUp(int index) {
        int parentIndex = (index - 1) / 2;
        while (index > 0 && heap[index] < heap[parentIndex]) {
            swap(index, parentIndex);
            index = parentIndex;
            parentIndex = (index - 1) / 2;
        }
    }

    // 删除堆顶元素
    public int extractMin() {
        if (size <= 0) {
            throw new IllegalStateException("堆为空");
        }
        int root = heap[0];
        heap[0] = heap[size - 1];
        size--;
        heapifyDown(0); // 维护堆的性质
        return root;
    }

    // 下沉操作
    private void heapifyDown(int index) {
        int smallest = index;
        int leftChild = 2 * index + 1;
        int rightChild = 2 * index + 2;

        if (leftChild < size && heap[leftChild] < heap[smallest]) {
            smallest = leftChild;
        }
        if (rightChild < size && heap[rightChild] < heap[smallest]) {
            smallest = rightChild;
        }

        if (smallest != index) {
            swap(index, smallest);
            heapifyDown(smallest);
        }
    }

    private void swap(int index1, int index2) {
        int temp = heap[index1];
        heap[index1] = heap[index2];
        heap[index2] = temp;
    }

    // 获取堆的大小
    public int getSize() {
        return size;
    }
}

堆的应用 - TOP-K 问题

TOP-K 问题是一个经典算法问题，任务是从给定的数组中找出最小的 K 个数字。这个问题可以使用最小堆来高效解决。

实现思路如下： 1. 创建一个大小为 K 的最小堆。 2. 遍历给定的数组： - 如果堆的大小小于 K，则将新元素加入堆。 - 如果堆已经满了且当前元素小于堆顶元素，则替换堆顶元素。 3. 最终，堆中的元素就是 K 个最小的数字。

下面是 Java 实现的代码示例：

import java.util.Arrays;

public class TopK {
    public static int[] findTopK(int[] nums, int k) {
        if (k <= 0 || k > nums.length) {
            throw new IllegalArgumentException("k的值不合法");
        }

        MinHeap minHeap = new MinHeap(k);

        for (int num : nums) {
            if (minHeap.getSize() < k) {
                minHeap.insert(num);
            } else if (num < minHeap.heap[0]) {
                minHeap.extractMin();
                minHeap.insert(num);
            }
        }

        return Arrays.copyOf(minHeap.heap, minHeap.getSize());
    }

    public static void main(String[] args) {
        int[] nums = {3, 1, 5, 12, 2, 11, 15, 8};
        int k = 3;
        int[] result = findTopK(nums, k);
        System.out.println("最小的 " + k + " 个数是: " + Arrays.toString(result));
    }
}

总结

在实际应用中，堆的使用能够极大地提高处理效率。通过最小堆的结构，可以在O(log K)的时间复杂度内处理 TOP-K 问题，让问题解决变得简单高效。希望本文能够对理解堆及其应用有所帮助。