Java数据结构之堆(优先队列)详解

概述

堆是一种基于树的数据结构，它可以用来解决很多问题，例如排序、优先队列等。在堆中，每个节点的值都小于或等于它的子节点的值。堆分为两种类型：最大堆和最小堆。在最大堆中，根节点的值最大；而在最小堆中，根节点的值最小。

堆的操作主要有以下两种：

• 插入：将一个元素插入到堆中，需要维护堆的性质，即节点的值小于或等于子节点的值。
• 删除：从堆中删除一个元素，需要维护堆的性质。

堆可以用数组来实现，也可以用树来实现。在数组中，每个元素的下标就相当于在树中的节点编号。在最大堆中，堆顶元素是最大的元素，在最小堆中，堆顶元素是最小的元素。

实现

在Java中，堆可以通过PriorityQueue来实现。PriorityQueue是一种优先队列，它维护了一个小根堆。

创建PriorityQueue

PriorityQueue<Integer> minHeap = new PriorityQueue<>();

创建一个空的PriorityQueue，可以通过指定一个Comparator来创建最大堆。

PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

插入元素

向PriorityQueue中插入一个元素。

minHeap.add(5);

删除元素

从PriorityQueue中删除一个元素。

minHeap.poll();

获取堆顶元素

获取PriorityQueue的堆顶元素。

minHeap.peek();

示例

以下是一个使用PriorityQueue来解决Top K问题的示例。

public int[] topK(int[] nums, int k) {
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    for (int i : nums) {
        minHeap.add(i);
        if (minHeap.size() > k) {
            minHeap.poll();
        }
    }
    int[] res = new int[k];
    int i = 0;
    while (!minHeap.isEmpty()) {
        res[i++] = minHeap.poll();
    }
    return res;
}

以上示例使用了一个大小为k的最小堆来解决Top K问题，时间复杂度为O(nlogk)。在遍历数组时，如果堆的大小超过了k，则删除堆顶元素。最后，Top K的元素就是堆中剩余的元素。

另一个示例是使用PriorityQueue来解决合并K个有序数组的问题。

public int[] mergeKSortedArrays(int[][] arrays) {
    PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> a[0] - b[0]);
    for (int i = 0; i < arrays.length; i++) {
        if (arrays[i].length > 0) {
            minHeap.add(new int[]{arrays[i][0], i, 0});
        }
    }
    int[] res = new int[arrays.length * arrays[0].length];
    int i = 0;
    while (!minHeap.isEmpty()) {
        int[] cur = minHeap.poll();
        res[i++] = cur[0];
        if (cur[2] < arrays[cur[1]].length - 1) {
            minHeap.add(new int[]{arrays[cur[1]][cur[2] + 1], cur[1], cur[2] + 1});
        }
    }
    return res;
}

以上示例使用了一个大小为K的最小堆来解决合并K个有序数组的问题，时间复杂度为O(nlogk)。在每次取堆顶元素时，将其从它所在的数组中的下一个元素插入到堆中。重复此步骤直到堆为空，这样就得到了合并后的有序数组。

结论

堆是一种非常有用的数据结构，可以用来解决很多问题。在Java中，可以使用PriorityQueue来实现堆的功能，并通过Comparator来实现最大堆和最小堆。PriorityQueue可以用来解决Top K问题和合并K个有序数组的问题。