文章目录
大家好，我是周一。
上次我们聊了堆和堆排序，这次我们就顺着说说和堆有关的题目。
一、几乎有序的数组排序
1、题目描述：
已知一个几乎有序的数组，几乎有序是指，如果把数组排好序的话，每个元素移动的距离一定不超过K，并且K相对于数组长度来说是比较小的。
请选择一个合适的排序策略，对这个数组进行排序。
2、解决思路：
从第一个数开始，
将前K+1个数放到小根堆里，弹出第一个数放到数组第一个位置；
将第K+2个数放到这个小根堆里，再弹出第一个数放到数组第二个位置；
将第K+3个数放到这个小根堆里，再弹出第一个数放到数组第三个位置；
直到小根堆为空
3、详细的参考代码：
public static void sortArrayDistanceLessK(int[] arr, int k) {
if (arr == null || arr.length < 2 || k == 0) {
return;
}
// 默认是小根堆
PriorityQueue<Integer> heap = new PriorityQueue<>();
// 标记当前已经放到堆中元素的数组下标
int index = 0;
// 将前k个数放进数组中
for (; index < k; index++) {
heap.add(arr[index]);
}
// 标记当前数组中已经排好序的下标
int i = 0;
// 从第k+1个数一直到数组最后一个数，
for (; index < arr.length; index++) {
// 每次放进堆中一个数，
heap.add(arr[index]);
// 同时弹出此时堆顶元素放到数组中，排序下标后移
arr[i++] = heap.poll();
}
// 将小根堆中剩余数据放到数组中
while (!heap.isEmpty()) {
arr[i++] = heap.poll();
}
}
4、时间复杂度为O(N*logK)
堆中只有K+1个数，也就是调整为小根堆的过程，时间复杂度是logK，因为需要遍历一遍整个数组，所以最后的时间复杂度是O(N*logK)。
二、最大线段重合问题
1、题目描述：
给定很多线段，每个线段都有两个数[start, end]，表示线段开始位置和结束位置，左右都是闭区间。
规定：
1）线段的开始位置和结束位置一定都是整数
2）两个线段重合的定义：线段重合区域的长度必须>=1才表示线段重合
求：线段最多的重合区域中，包含了几条线段。
2、解决思路：
1）将所有线段按照开始位置从小到大排序，同时准备一个小根堆用于存放线段结束位置
2）遍历排序后的所有线段，将此时小根堆里小于等于此时线段开始位置的数弹出，同时将此时线段结束位置的数放到小根堆里，此时小根堆的个数即是从此时线段开始位置作为重合区域左边界的重合区域所包含线段的个数。（任何重合区域的左边界必定是某个线段的左边界）
因为此时小根堆里的数表示之前线段的右边界会穿过此时线段的左边界，而之前线段的左边界是小于此时线段的左边界的，所以小根堆的个数即是重合区域中包含线段的个数。
3）最后第2步中 最大的个数 即是 包含线段最多的重合区域中所包含的线段数
3、详细的参考代码：
public static class Line {
private int start;
private int end;
public Line(int start, int end) {
this.start = start;
this.end = end;
}
}
/**
* 时间复杂度 O(N*logN)
*/
public static int lineCoverMaxByHeap(int[][] n) {
Line[] lines = new Line[n.length];
for (int i = 0; i < n.length; i++) {
lines[i] = new Line(n[i][0], n[i][1]);
}
// 将所有线段按照开始下标从小到大排序
Arrays.sort(lines, (o1, o2) -> o1.start - o2.start);
// 准备一个小根堆（存放线段的结束值）
PriorityQueue<Integer> heap = new PriorityQueue<>();
int cover = 0;
for (Line line : lines) { // O(N)
// 将小根堆中所有小于等于当前线段开始值的数据弹出
while (!heap.isEmpty() && heap.peek() <= line.start) { // O(logN)
heap.poll();
}
// 将当前线段的结束值放到小根堆中
heap.add(line.end);
cover = Math.max(cover, heap.size());
}
return cover;
}
全部代码：https://github.com/monday-pro/algorithm-study/tree/master/src/basic/heap