027【必备】堆结构常见题
前置知识：讲解025-堆结构和堆排序、讲解026-比较器
题目1:合并K个有序链表
题目2:线段最多重合问题
题目3:让数组整体累加和减半的最少操作次数
23. 合并 K 个升序链表
或者牛客：https://www.nowcoder.com/practice/65cfde9e5b9b4cf2b6bafa5f3ef33fa6
首先补充：
Java 的 PriorityQueue 是一种基于优先级堆（Priority Heap）的数据结构，具体来说，它通常是基于最小堆（Min-Heap）实现的。堆是一种特殊的二叉树结构，满足堆属性：在最小堆中，父节点的值总是小于或等于其子节点的值。
- 插入（offer/add）：将元素添加到堆中，并通过“上浮”（sift-up）操作维护堆的性质，时间复杂度为 O(log n)。
- 删除最小元素（poll/remove）：移除并返回堆顶元素（最小值），然后通过“下沉”（sift-down）操作调整堆，时间复杂度为 O(log n)。
- 查看顶部元素（peek）：返回但不移除堆顶元素，时间复杂度为 O(1)。
不保证除堆顶外的元素完全有序，仅保证堆顶是最小（或最大，取决于比较器）的元素。
注意比较器的定制：
等价于Lambda写法：
等价于：
解法:小根堆
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
* 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) {
// 边界检查：如果 lists 为 null 或空，直接返回 null
if (lists == null || lists.length == 0) return null;
// 使用 PriorityQueue，按节点值升序排序
PriorityQueue<ListNode> pq = new PriorityQueue<>(Comparator.comparingInt(o -> o.val));
// 将所有非空链表的头节点加入优先级队列
for (ListNode node : lists) {
if (node != null) pq.offer(node);
}
// 如果队列为空，说明没有有效节点，返回 null
if (pq.isEmpty()) return null;
// 取出第一个节点作为头节点
ListNode head = pq.poll();
// 如果头节点的下一个节点不为空，加入队列
if (head != null && head.next != null) pq.offer(head.next);
// 当前指针指向头节点
ListNode cur = head;
// 从优先级队列中依次取出节点，构建结果链表
while (!pq.isEmpty()) {
cur.next = pq.poll();
cur = cur.next;
if (cur.next != null) pq.offer(cur.next);
}
return head;
}
}
上面解法的时间复杂度是\(O(n*logk)\)， 空间复杂度是\(O(k)\)，其中n是节点总数，k是链表数量。
更简单的题：21. 合并两个有序链表
最多线段重合问题
测试链接 : https://www.nowcoder.com/practice/1ae8d0b6bb4e4bcdbf64ec491f63fc37 测试链接 : https://leetcode.cn/problems/meeting-rooms-ii/
给你一个会议时间安排的数组 intervals ，每个会议时间都会包括开始和结束的时间 intervals[i] = [starti, endi] ，返回 所需会议室的最小数量 。
示例 1：
1
2
输入：intervals = [[0,30],[5,10],[15,20]]
输出：2
示例 2：
1
2
输入：intervals = [[7,10],[2,4]]
输出：1
提示：
1 <= intervals.length <= 1040 <= starti < endi <= 106
1
2
3
4
5
class Solution {
public int minMeetingRooms(int[][] intervals) {
}
}
解法:任何重合区域的左边界一定是某个线段的左边界
思路是：以[[0,30],[5,10],[15,20]]举例
- 对于每个线段的左边界进行排序（升序）。即0， 5， 15是排序之后的。所以变成了
[[0,30],[5,10],[15,20]] - 然后准备一个小根堆。每次遍历到一个线段
[X, Y]首先将堆中<=X的全部弹出，然后把Y放进小根堆。记录此时小根堆中的元素的个数。记作\(size_i\) - 每次记录的\(size_i\)选出最大值就是最终的答案，即最多线段重合的个数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public int minMeetingRooms(int[][] intervals) {
PriorityQueue<Integer> pq = new PriorityQueue<>();
// 对于每个线段的左边界进行排序（升序）
int res = 0;
Arrays.sort(intervals, (o1, o2) -> o1[0] - o2[0]);
for (int[] i : intervals) {
while ((!pq.isEmpty()) && pq.peek() <= i[0]) {
pq.poll();
}
pq.offer(i[1]);
res = Math.max(pq.size(), res);
}
return res;
}
}
牛客：线段重合
测试链接 : https://www.nowcoder.com/practice/1ae8d0b6bb4e4bcdbf64ec491f63fc37
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
import java.io.*;
import java.util.Arrays;
public class Main {
public static int MAXN = 10001;
public static int[][] line = new int[MAXN][2];
public static int n;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StreamTokenizer in = new StreamTokenizer(br);
PrintWriter out = new PrintWriter(System.out);
while (in.nextToken() != StreamTokenizer.TT_EOF) {
n = (int)in.nval;
for (int i = 0;i < n;i++) {
in.nextToken();
line[i][0] = (int)in.nval;
in.nextToken();
line[i][1] = (int)in.nval;
}
out.println(compute());
}
out.flush();
out.close();
br.close();
}
public static int[] heap = new int[MAXN];
public static int size;
public static int compute() {
// 清空堆
size = 0;
Arrays.sort(line, 0, n, (a, b) -> a[0] - b[0]);
int ans = 0;
for (int i = 0;i < n;i++) {
while (size > 0 && heap[0] <= line[i][0]) {
pop();
}
add(line[i][1]);
ans = Math.max(size, ans);
}
return ans;
}
public static void add(int x) {
heap[size] = x;
int i = size++;
while (heap[i] < heap[(i - 1) / 2]) {
swap(i, (i - 1) / 2);
i = (i - 1) / 2;
}
}
public static void pop() {
swap(0, --size);
int i = 0, l = 1;
while (l < size) {
int best = l + 1 < size && heap[l + 1] < heap[l] ? l + 1 : l;
best = heap[best] < heap[i] ? best : i;
if (best == i) {
break;
}
swap(best, i);
i = best;
l = i * 2 + 1;
}
}
public static void swap(int i, int j) {
int t = heap[i];
heap[i] = heap[j];
heap[j] = t;
}
}
上面的leetcode题目是会员题，需要付费
如果不想开通leetcode会员，还有一个类似的题，但是注意题意，和课上讲的有细微差别
课上讲的题目，认为[1,4]、[4、5]可以严丝合缝接在一起，不算有重合
但是如下链接的题目，认为[1,4]、[4、5]有重合部分，也就是4
除此之外再无差别
测试链接 : https://leetcode.cn/problems/divide-intervals-into-minimum-number-of-groups/
2208. 将数组和减半的最少操作次数
给你一个正整数数组 nums 。每一次操作中，你可以从 nums 中选择 任意 一个数并将它减小到 恰好 一半。（注意，在后续操作中你可以对减半过的数继续执行操作）
请你返回将 nums 数组和 至少 减少一半的 最少 操作数。
示例 1：
1
2
3
4
5
6
7
8
9
10
11
输入：nums = [5,19,8,1]
输出：3
解释：初始 nums 的和为 5 + 19 + 8 + 1 = 33 。
以下是将数组和减少至少一半的一种方法：
选择数字 19 并减小为 9.5 。
选择数字 9.5 并减小为 4.75 。
选择数字 8 并减小为 4 。
最终数组为 [5, 4.75, 4, 1] ，和为 5 + 4.75 + 4 + 1 = 14.75 。
nums 的和减小了 33 - 14.75 = 18.25 ，减小的部分超过了初始数组和的一半，18.25 >= 33/2 = 16.5 。
我们需要 3 个操作实现题目要求，所以返回 3 。
可以证明，无法通过少于 3 个操作使数组和减少至少一半。
示例 2：
1
2
3
4
5
6
7
8
9
10
11
输入：nums = [3,8,20]
输出：3
解释：初始 nums 的和为 3 + 8 + 20 = 31 。
以下是将数组和减少至少一半的一种方法：
选择数字 20 并减小为 10 。
选择数字 10 并减小为 5 。
选择数字 3 并减小为 1.5 。
最终数组为 [1.5, 8, 5] ，和为 1.5 + 8 + 5 = 14.5 。
nums 的和减小了 31 - 14.5 = 16.5 ，减小的部分超过了初始数组和的一半， 16.5 >= 31/2 = 15.5 。
我们需要 3 个操作实现题目要求，所以返回 3 。
可以证明，无法通过少于 3 个操作使数组和减少至少一半。
提示：
1 <= nums.length <= 1051 <= nums[i] <= 107
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public int halveArray(int[] nums) {
// 大根堆 需要自己写比较器
PriorityQueue<Long> heap = new PriorityQueue<>((a, b) -> b.compareTo(a));
// 求和
long sum = 0;
for (int i = 0;i < nums.length;i++) {
sum += ((long)nums[i] << 20);
heap.add((long)nums[i] << 20);
}
long target = sum >> 1;
long curSum = sum;
int ans = 0;
while (curSum > target) {
long pollHalf = (heap.poll() >> 1);
curSum -= (pollHalf);
heap.add(pollHalf);
ans++;
}
return ans;
}
}
这个解法可以通过，但不是很快，可以考虑自己实现一个大根堆。
用数组实现大根堆，这道题解法如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
class Solution {
// public int halveArray(int[] nums) {
// // 大根堆 需要自己写比较器
// PriorityQueue<Long> heap = new PriorityQueue<>((a, b) -> b.compareTo(a));
// // 求和
// long sum = 0;
// for (int i = 0;i < nums.length;i++) {
// sum += ((long)nums[i] << 20);
// heap.add((long)nums[i] << 20);
// }
// long target = sum >> 1;
// long curSum = sum;
// int ans = 0;
// while (curSum > target) {
// long pollHalf = (heap.poll() >> 1);
// curSum -= (pollHalf);
// heap.add(pollHalf);
// ans++;
// }
// return ans;
// }
long[] heap;
int size;
public int halveArray(int[] nums) {
int N = nums.length;
heap = new long[N];
size = 0;
// 求和
long sum = 0;
for (int i = 0;i < N;i++) {
sum += ((long)nums[i] << 20);
// add
add((long) nums[i] << 20);
}
long target = sum >> 1;
long curSum = sum;
int ans = 0;
while (curSum > target) {
long pollHalf = (heap[0] >> 1);
pop();
curSum -= (pollHalf);
add(pollHalf);
ans++;
}
return ans;
}
public void add(long x) {
heap[size] = x;
int i = size++;
while (heap[i] > heap[(i - 1) / 2]) {
swap(i, (i - 1) / 2);
i = (i - 1) / 2;
}
}
public void swap(int i, int j) {
long t = heap[i];
heap[i] = heap[j];
heap[j] = t;
}
public void pop() {
swap(0, --size);
int i = 0, l = 1;
while (l < size) {
int best = l + 1 < size && heap[l + 1] > heap[l] ? l + 1 : l;
best = heap[i] > heap[best] ? i : best;
if (best == i) {
break;
}
swap(i, best);
i = best;
l = 2 * i + 1;
}
}
}
