算法通关村——解析堆在数组和链表的应用

1. 堆

1.1 什么是堆？

堆是将一组数据以完全二叉树的形式存储在数组里面。一般有大根堆和小根堆。
小根堆：任意节点的值小于等于它的左右孩子，最小值在堆顶。
大根堆：任意节点的值大于等于它的左右还是，最大值在堆顶。
java里面采用PriorityQueue，然后可以自定义构建小根堆，大根堆。
在这里插入图片描述

2. 数组中的第K个最大元素

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

2.1 小根堆

主要思路就是使用一个小根堆来存储前k个元素，然后再遍历k后面的元素，如果有元素大于队首元素，队首元素出队，该元素入队，否则继续遍历。

输入: [3,2,1,5,6,4], k = 2
输出: 5

k=2，创建容量为2的小根堆，先添加3，2元素，堆元素[2,3]
1进入，1<2, 继续
5入队，5>2，2出队，5入队，堆元素[3,5]
6入队，6>3，3出队，6入队，堆元素[5,6]
4<5，继续，退出，第k个最大元素就是5

 public int findKthLargest(int[] nums, int k) {int len = nums.length;if(k>len){return -1;}// 小根堆PriorityQueue<Integer> pq = new PriorityQueue<Integer>(k,(a,b)->a-b);// 添加前k个元素for(int i=0;i<k;i++){pq.add(nums[i]);}for(int i=k;i<len;i++){// 堆顶元素Integer top = pq.peek();// 堆顶元素小，堆顶元素出栈，当前元素入栈if(nums[i] > top){pq.poll();pq.offer(nums[i]);}}return pq.peek();}

3. 合并 K 个升序链表

给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
合并K个升序链表

3.1 小根堆

构建一个小根堆，让里面的每个列表的头节点添加到堆里面，然后创建一个新的链表，将最小的元素添加到链表里面，这个最小的元素后面如果还有其他元素的话，就将其他元素添加至堆里面，进一步排序，然后再刷选出最小的节点。

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
1->4->5,
1->3->4,
2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

堆里面初始：头节点 1，1，2
第一次合并到新链表，1里面还剩[1,3,4]，[2,6]，[4,5] 头节点1，2，4 , 链表 1 ->
第二次合并 [2,6][3,4] [4,5], 头节点2，3，4，链表 1->1->
第三次合并 [6][3,4][4,5] 头节点3，4，5，链表 1->1->2
依次合并

public ListNode mergeKLists(ListNode[] lists) {if(lists == null){return null;}// 构建小根堆PriorityQueue<ListNode> pq = new PriorityQueue<ListNode>(Comparator.comparing(node->node.val));for(int i=0;i<lists.length;i++){if(lists[i]!=null){pq.add(lists[i]);}}ListNode sentinel = new ListNode(-1);ListNode res = sentinel;while(!pq.isEmpty()){// 合并后链表里面最小值res.next = pq.poll();res = res.next;if(res.next!=null){pq.add(res.next);}}return sentinel.next;}