Java数据结构之堆(优先队列)的实现
时间：2023-02-02 10:13:07 | 栏目：JAVA代码 | 点击：次
堆（优先队列）是一种典型的数据结构，其形状是一棵完全二叉树，一般用于求解topk问题。根据双亲节点大于等于孩子节点或双亲节点小于等于孩子节点，可分为大顶堆和小顶堆，本文实现大顶堆。
根据大顶堆的定义，大顶堆的双亲节点大于等于其孩子节点，堆顶元素最大，对于每一个子树都是一个大顶堆，则从最后一个双亲节点进行调整为大顶堆，一直到根节点，则可构建一个大顶堆。
我们这里采用数组去存储，以heap={3,2,1,5,6,4}为例，需要一个init(int[] heap)初始化方法，从最后一个双亲节点开始将heap逐渐调整为大顶堆，其中需要使用到adjust(int[] heap, int i, int end)方法。
调整过程：从最后一个双亲节点出发，如果以当前双亲节点为根的树不符合大顶堆，则进行调整。
代码实现如下：
public void init(int[] heap) {
//从最后一个双亲节点开始调整
//逐渐往上进行调整
for (int i = heap.length / 2 ; i > 0 ; i-- ) {
this.adjust(heap, i, heap.length);
}
}
public void adjust(int[] heap, int i, int end) {
int j = i << 1;
while (j <= end) {
//找到两个孩子节点z中较大的节点
if (j < end && heap[j - 1] < heap[j]) {
j = j + 1;
}
//如果较大节点还小于根节点，则以当前节点为根节点的
//二叉树已经是大顶堆，不需要进行调整
if (heap[i - 1] > heap[j - 1]) {
break;
}
//进行调整，将当前节点换到较大位置，再从当前位置进行调整
int temp = heap[i - 1];
heap[i - 1] = heap[j - 1];
heap[j - 1] = temp;
i = j;
j = i << 1;
}
}
构建好了大顶堆之后，我们如何求得topk呢，此时堆顶元素为top1，我们只需要将top1元素拿走，将剩下元素调整为大顶堆，k次之后即可得到topk。
具体过程：我们将堆顶元素与最后一个元素进行交换，然后将堆顶到倒数第二个元素进行调整，依次类推。
以leetcode215数组中第k个最大元素为例：
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素
public int findKthLargest(int[] nums, int k) {
this.init(nums);
//找到第k大的数
int end = nums.length;
while (k > 1) {
//将当前堆顶元素放到末尾，进行堆调整
int temp = nums[0];
nums[0] = nums[end - 1];
nums[end - 1] = temp;
end = end - 1;
-- k;
this.adjust(nums, 1, end);
}
return nums[0];
}
此外，Java本身提供了优先队列集合类，但是对于这个题目效率不如自己实现的高
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(k);
for (int num : nums) {
if (priorityQueue.size() == k) {
if (num > priorityQueue.peek()) {
priorityQueue.poll();
priorityQueue.add(num);
}
continue;
}
priorityQueue.add(num);
}
return priorityQueue.poll();
}
