算法与数据体系课笔记之-7.加强堆与堆结构相关题目

7.加强堆与堆相关题目分析 总览笔记思维导图链接常见题目汇总：

题1：**最大线段重合问题（堆实现）**

题目描述：题解：代码实现：复杂度分析：

算法与数据结构思维导图

参考左程云算法课程

给定很多线段，每个线段都有两个数组[start, end]，

表示线段开始位置和结束位置，左右都是闭区间

规定：
1）线段的开始和结束位置一定都是整数值
2）线段重合区域的长度必须>=1

返回线段最多重合区域中，包含了几条线段

package class07;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class Code01_CoverMax {
	// 创建line线段类对象，将二维数组对象转为线段对象，方便处理arr[a,b]->line(a,b)
	public static class Line {
		private int start;
		private int end;

		public Line(int start, int end) {
			super();
			this.start = start;
			this.end = end;
		}
	}

	// 方法1：暴力统计算法
	public static int maxCover1(int[][] lines) {
		// 1. 确定线段最小和最大范围，锁定要校验的对象
		int min = Integer.MAX_VALUE;
		int max = Integer.MIN_VALUE;
		for (int i = 0; i < lines.length; i++) {
			min = Math.min(min, lines[i][0]);
			max = Math.max(max, lines[i][1]);
		}
		// 2. 以每个在范围内的数的.5为基点，遍历统计包含该数的所有线段数
		int cover = 0;
		for (double p = min + 0.5; p < max; p += 1) {
			int cur = 0;
			for (int i = 0; i < lines.length; i++) {
				if (lines[i][0] < p && lines[i][1] > p) {
					cur++;
				}
			}
			cover = Math.max(cover, cur);
		}
		return cover;
	}

	// 方法2：使用最小堆结构
	public static int maxCover2(int[][] m) {
		// 1. 将线段按照左边界大小进行排序
		// 先将二维数组转为线段对象，方便比较排序处理
		// 将各二维数组new出线段对象放在一个一维的线段类型数组中
		Line[] lines = new Line[m.length];
		for (int i = 0; i < lines.length; i++) {
			lines[i] = new Line(m[i][0], m[i][1]);
		}
		Arrays.sort(lines, (a, b) -> a.start - b.start);

		// 2. 依次遍历所有左边界，并维护最小堆
		PriorityQueue minHeap = new PriorityQueue<>();
		int res = 0;
		for (int i = 0; i < lines.length; i++) {
			// 弹入前，先判断弹出不满足的线段
			// 注意，等于也弹出，等于，说明线段相连，重合部分为0
			while (!minHeap.isEmpty() && lines[i].start >= minHeap.peek())
				minHeap.poll();
			// 弹干净后，再弹入右边界值
			minHeap.add(lines[i].end);
			// 3. 统计每个基点的重合线段数，并比较出最大值
			res = Math.max(res, minHeap.size());
		}
		return res;
	}

	// for test
	public static int[][] generateLines(int N, int L, int R) {
		int size = (int) (Math.random() * N) + 1;
		int[][] ans = new int[size][2];
		for (int i = 0; i < size; i++) {
			int a = L + (int) (Math.random() * (R - L + 1));
			int b = L + (int) (Math.random() * (R - L + 1));
			if (a == b) {
				b = a + 1;
			}
			ans[i][0] = Math.min(a, b);
			ans[i][1] = Math.max(a, b);
		}
		return ans;
	}
	
	public static class StartComparator implements Comparator {

		@Override
		public int compare(Line o1, Line o2) {
			return o1.start - o2.start;
		}

	}

	public static void main(String[] args) {

		Line l1 = new Line(4, 9);
		Line l2 = new Line(1, 4);
		Line l3 = new Line(7, 15);
		Line l4 = new Line(2, 4);
		Line l5 = new Line(4, 6);
		Line l6 = new Line(3, 7);

		// 底层堆结构，heap
		PriorityQueue heap = new PriorityQueue<>(new StartComparator());
		heap.add(l1);
		heap.add(l2);
		heap.add(l3);
		heap.add(l4);
		heap.add(l5);
		heap.add(l6);

		while (!heap.isEmpty()) {
			Line cur = heap.poll();
			System.out.println(cur.start + "," + cur.end);
		}

		System.out.println("test begin");
		int N = 100;
		int L = 0;
		int R = 200;
		int testTimes = 200000;
		for (int i = 0; i < testTimes; i++) {
			int[][] lines = generateLines(N, L, R);
			int ans1 = maxCover1(lines);
			int ans2 = maxCover2(lines);
			if (ans1 != ans2) {
				System.out.println("Oops!");
			}
		}
		System.out.println("test end");
	}
}

1.线段排序为O(NlogN)

2.循环遍历左边界，并维护最小堆，统计比较O(NlogN)：

​ for循环: 所有线段考察一次O(N)
​ 小根堆复杂度: 所有线段结尾位置, 最多进一次, 最多出一次, 一共进出2N
​ 小根堆每次调整代价logN(shiftUP,shiftDownd堆化都是logn)

总复杂度O(N*logN)