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 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();

}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。