算法通关村十四关：白银挑战-堆能高效解决的经典问题

白银挑战-堆能高效解决的经典问题

1.在数组中找第K大的元素

LeetCode215
https://leetcode.cn/problems/kth-largest-element-in-an-array/

思路分析

主要解决方法有3个，选择法，堆查找法和快速排序法

方法1：选择法
先遍历一遍找到最大的元素，再遍历一遍找第二大的，依次直到第K次就找到了目标值了

方法2：堆排序法
用大堆和小堆都可以，推荐"找最大用小堆，找最小用大堆，找中间用两个堆"

构造一个大小只有k的小根堆
堆满了之后，对于小根堆，并不一定所有新来的元素都可以入堆的，只有大于根元素的才可以插入到堆中，否则直接抛弃
完成之后此时根元素恰好时当前序列下第K大的元素

代码实现：
代码自己实现起来比较困难，可以使用jdk的优先队列来解决

• 维护一个有k个元素的最小堆
• 如果当前堆不满，直接添加
• 堆满的时候，如果新读到的数小于堆顶，不操作；如果大于堆顶，将堆顶拿出，然后放入新读到的数，进而让堆自己调整内部结构

方法3：快速排序法
之前已经分析过了，见前面内容

代码实现

import java.util.PriorityQueue;class Solution {public int findKthLargest(int[] nums, int k) {if(k>nums.length){return -1;}int len = nums.length;// 使用一个含有k个元素的最小堆PriorityQueue<Integer> minHeap = new PriorityQueue<>(k, (a, b) -> a-b);for (int i = 0; i<k; i++){minHeap.add(nums[i]);}for(int i=k; i<len; i++){// 看一眼，不拿出，因为有可能没有必要替换Integer topEle = minHeap.peek();// 只要当前遍历的元素比堆顶元素大，堆顶弹出，遍历的元素进去if (nums[i] > topEle){minHeap.poll();minHeap.offer(nums[i]);}}return minHeap.peek();}
}

python中没有现成的二叉堆，要自己实现部分功能
参考：https://leetcode.cn/problems/kth-largest-element-in-an-array/solutions/1507044/by-flix-amc8/

2.堆排序原理

排序：升序用小，降序用大

大顶推：
根结点是整个结构最大的元素
将根结点拿走，剩下的重排，此时根结点就是第二大的元素
再拿走根结点，再排
以此类推，最后堆中只剩最后一个元素，此时拿走的数据也就排好序了

拿走重排的具体过程：移除堆顶元素，把下标为n的元素放到堆顶，再通过堆化的方法，将剩下的n-1个元素重新构建成堆

小顶堆与大顶堆类似

3.合并k个排序链表

LeetCode23. 合并 K 个升序链表
https://leetcode.cn/problems/merge-k-sorted-lists/

思路分析
问题有很多种方法，现在看使用堆排序如何解决

因为每个队列都是从小到大排序的，每次都要找最小的元素，所以用小根堆；
堆的大小定义，给了几个链表，堆就定义多大；
每次都将剩余节点的最小值加到输出链表尾部，然后进行堆调整；
最后堆空的时候，合并也就完成了。

代码实现

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode mergeKLists(ListNode[] lists) {if (lists == null || lists.length == 0){return null;}PriorityQueue<ListNode> q = new PriorityQueue<>(Comparator.comparing(node -> node.val));for (int i = 0; i<lists.length; i++){if(lists[i] != null){q.add(lists[i]);}}ListNode dummy = new ListNode(0);ListNode tail = dummy;while(!q.isEmpty()){tail.next = q.poll();tail = tail.next;if(tail.next != null){q.add(tail.next);}}return dummy.next;}
}