【算法&数据结构体系篇class06】：堆、大根堆、小根堆、优先队列

分手后的思念是犯贱 2024-03-26 10:38 33阅读 0赞

### 一、堆结构 ###

> 1）堆结构就是用数组实现的完全二叉树结构  
> 2）完全二叉树中如果每棵子树的最大值都在顶部就是大根堆  
> 3）完全二叉树中如果每棵子树的最小值都在顶部就是小根堆  
> 4）堆结构的heapInsert与heapify操作  
> 5）堆结构的增大add和减少poll  
> 6）优先级队列结构，就是堆结构

*  **heapInsert：**

入堆排序操作，从数组最后一个位置插入，然后再与其父节点(i-1)/2比较大小，大则交换上去，接着往其爷节点持续走..直到顶，或小于当前节点的父节点则停止，完成排序

*  **heapify:**

堆下沉排序操作 剔除元素后，需要将交换到根部的元素往下沉判断排序，如果大于左右节点就不用动，小于则与左右较大节点交换，并下沉继续判断，直到底部或者大于左右子节点

**代码演示：**

package class06;
    
    import java.util.Comparator;
    import java.util.PriorityQueue;
    
    public class Heap {
        //大根堆 每个子树根节点比左右节点大
        public static class MyMaxHeap {
            private int[] heap;
            private int heapSize;
            private final int limit;
    
            public MyMaxHeap(int limit) {
                heap = new int[limit];
                heapSize = 0;
                this.limit = limit;
            }
    
            public boolean isEmpty() {
                return heapSize == 0;
            }
    
            public boolean isFull() {
                return limit == heapSize;
            }
    
            //入堆，同时保持堆的大根堆 有序
            public void push(int value) {
                if (isFull()) {
                    throw new RuntimeException("堆已满，无法添加元素！");
                }
                //没满就赋值追加到数组后
                heap[heapSize] = value;
                //依次与该元素的父节点比较大小，大则交换两元素，然后接着往上走，直到顶或者不大于父节点,同时最后要把size+1
                heapInsert(heap, heapSize++);
            }
    
            //入堆操作，从数组最后一个位置插入，然后再与其父节点(i-1)/2比较大小，大则交换上去，接着往其爷节点持续走..直到顶，或小于当前节点的父节点则停止，完成排序
            private void heapInsert(int[] heap, int i) {
                //这个条件判断了两种情况，一个是大于父节点，一个是还没到顶节点（假如i来到顶部0 那么(i-1)/2也等0 为自己，是等于） 则继续循环。
                while (heap[i] > heap[(i - 1) / 2]) {
                    swap(heap, i, (i - 1) / 2);
                    i = (i - 1) / 2;
                }
            }
    
            //出堆，弹出最大值，顶部，然后保证当前堆仍有序 是大根堆
            public int pop() {
                if (isEmpty()) {
                    throw new RuntimeException("堆已空，无法弹出元素！");
                }
                //弹出首元素，最大值
                int ans = heap[0];
                //然后把元素剔除两步  1.将首元素，与尾元素（heapSize是长度，尾元素是heapSize-1）交换，因为弹出操作，需要将heapSize 元素个数-1，两个操作只需要用--heapSize就能符合
                swap(heap, 0, --heapSize);
                //2.交换后表示将根节点元素剔除，然后需要确保现有堆的顺序
                heapify(heap, 0, heapSize);
                return ans;
            }
    
            //堆下沉排序操作 剔除元素后，需要将交换到根部的元素往下沉判断排序，如果大于左右节点就不用动，小于则与左右较大节点交换，并下沉继续判断，直到底部或者大于左右子节点
            private void heapify(int[] heap, int i, int heapSize) {
                //首先判断是否存在左子节点，左节点索引是i*2+1,不能超过heapSize-1尾索引，如果超过那肯定就到最后一个元素，右节点是比左节点大1 也更不会存在
                while (i * 2 + 1 < heapSize) {
                    //此时确定有左节点，但需要判断是否有右节点i*2+2 如果有 并且大于左节点，那么左右节点较大值就是右节点，否则就是左节点
                    int largest = i*2+2 < heapSize && heap[i*2+2]>heap[i*2+1]?i*2+2:i*2+1;
                    //然后把较大的节点与父节点比较，谁大则重新赋值 largest最大值
                    largest = heap[largest] > heap[i]?largest:i;
                    if(largest == i) break; //如果判断后这个最大值位置就是父节点位置，相当于父节点都大于子节点，那么就不用交换,再下沉，此时已经完成排序，大的仍旧在前面，小的在下面，直接退出循环
                    //子节点大于当前节点，那么与其较大的节点交换，交换完之后，当前节点i要来到较大节点largest位置 循环下沉
                    swap(heap,i,largest);
                    i = largest;
                }
            }
            private void swap(int[] heap, int i, int j) {
                int temp = heap[i];
                heap[i] = heap[j];
                heap[j] = temp;
            }
        }
    
        public static class RightMaxHeap {
            private int[] arr;
            private final int limit;
            private int size;
    
            public RightMaxHeap(int limit) {
                arr = new int[limit];
                this.limit = limit;
                size = 0;
            }
    
            public boolean isEmpty() {
                return size == 0;
            }
    
            public boolean isFull() {
                return size == limit;
            }
    
            public void push(int value) {
                if (size == limit) {
                    throw new RuntimeException("heap is full");
                }
                arr[size++] = value;
            }
    
            public int pop() {
                int maxIndex = 0;
                for (int i = 1; i < size; i++) {
                    if (arr[i] > arr[maxIndex]) {
                        maxIndex = i;
                    }
                }
                int ans = arr[maxIndex];
                arr[maxIndex] = arr[--size];
                return ans;
            }
    
        }
    
        //比较器用于排序
        public static class MyComparator implements Comparator<Integer>{
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2-o1; //降序
            }
        }
    
        public static void main(String[] args) {
    
            // 大根堆   优先队列默认是小根堆，通过比较器降序排序实现大根堆
            PriorityQueue<Integer> heap = new PriorityQueue<>(new MyComparator());
            heap.add(5);
            heap.add(5);
            heap.add(5);
            heap.add(3);
            // 5 , 3
            System.out.println(heap.peek());
            heap.add(7);
            heap.add(0);
            heap.add(7);
            heap.add(0);
            heap.add(7);
            heap.add(0);
            System.out.println(heap.peek());
            while (!heap.isEmpty()) {
                System.out.println(heap.poll());
            }
    
            int value = 1000;
            int limit = 100;
            int testTimes = 1000000;
            for (int i = 0; i < testTimes; i++) {
                int curLimit = (int) (Math.random() * limit) + 1;
                MyMaxHeap my = new MyMaxHeap(curLimit);
                RightMaxHeap test = new RightMaxHeap(curLimit);
                int curOpTimes = (int) (Math.random() * limit);
                for (int j = 0; j < curOpTimes; j++) {
                    if (my.isEmpty() != test.isEmpty()) {
                        System.out.println("Oops!");
                    }
                    if (my.isFull() != test.isFull()) {
                        System.out.println("Oops!");
                    }
                    if (my.isEmpty()) {
                        int curValue = (int) (Math.random() * value);
                        my.push(curValue);
                        test.push(curValue);
                    } else if (my.isFull()) {
                        if (my.pop() != test.pop()) {
                            System.out.println("Oops!");
                        }
                    } else {
                        if (Math.random() < 0.5) {
                            int curValue = (int) (Math.random() * value);
                            my.push(curValue);
                            test.push(curValue);
                        } else {
                            if (my.pop() != test.pop()) {
                                System.out.println("Oops!");
                            }
                        }
                    }
                }
            }
            System.out.println("finish!");
    
        }
    }

### 二、堆排序，默认都是升序排序 ###

> 1，先让整个数组都变成大根堆结构，建立堆的过程:   
>  1)从上到下的方法，时间复杂度为O(N\*logN)   
>  2)从下到上的方法，时间复杂度为O(N)   
> 2，把堆的最大值和堆末尾的值交换，然后减少堆的大小之后，再去调整堆，一直周而复始，时间复杂度为O(N\*logN)   
> 3，堆的大小减小成0之后，排序完成

*  手写堆结构来进行排序操作

**代码演示：**

package class06;
    
    import java.util.Arrays;
    import java.util.PriorityQueue;
    
    public class HeapSort {
        /**
         * 堆排序 利用堆的heapInsert heapify操作实现
         * @param arr
         */
        public static void heapSort(int[] arr){
            if(arr == null || arr.length < 2) return;
            //1.先使数组转换成一个大根堆，heapInsert heapify都可以 后者的时间复杂度更低,从下往上 时间复杂度O(N)
           int heapSize = arr.length;
            for(int i = arr.length-1;i>=0;i--){
                heapify(arr,i,heapSize);
            }
            //O(N*logN)
    //        for(int i = 0;i<arr.length;i++){
    //            heapInsert(arr,i);
    //        }
            //2、首位交换，把最大值放到尾部，因为排序我们按降序，最大值就是放到尾部
            swap(arr,0,--heapSize);
            //3.依次开始进行堆下沉操作 直到排完序
            // O(N*logN)
            while(heapSize > 0){ //O(N)
                heapify(arr,0,heapSize); //O(logN)
                swap(arr,0,--heapSize); //O(1)
            }
        }
        public static void heapInsert(int[] arr, int i){
            while ( arr[i] > arr[(i-1)/2]){
                swap(arr,i,(i-1)/2);
                i = (i-1)/2;
            }
        }
        public static void heapify(int[] arr, int i, int heapSize){
            int left = i*2+1;
            while(left < heapSize){
                int largest = left + 1 < heapSize && arr[left + 1] >arr[left]?left+1:left;
                largest = arr[largest] > arr[i] ? largest : i;
                if(largest == i) break;
                swap(arr,i,largest);
                i = largest;
                left = i*2+1;
            }
        }
    
        private static void swap(int[] arr, int i, int j) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    
        // for test
        public static void comparator(int[] arr) {
            Arrays.sort(arr);
        }
    
        // for test
        public static int[] generateRandomArray(int maxSize, int maxValue) {
            int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
            for (int i = 0; i < arr.length; i++) {
                arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
            }
            return arr;
        }
    
        // for test
        public static int[] copyArray(int[] arr) {
            if (arr == null) {
                return null;
            }
            int[] res = new int[arr.length];
            for (int i = 0; i < arr.length; i++) {
                res[i] = arr[i];
            }
            return res;
        }
    
        // for test
        public static boolean isEqual(int[] arr1, int[] arr2) {
            if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
                return false;
            }
            if (arr1 == null && arr2 == null) {
                return true;
            }
            if (arr1.length != arr2.length) {
                return false;
            }
            for (int i = 0; i < arr1.length; i++) {
                if (arr1[i] != arr2[i]) {
                    return false;
                }
            }
            return true;
        }
    
        // for test
        public static void printArray(int[] arr) {
            if (arr == null) {
                return;
            }
            for (int i = 0; i < arr.length; i++) {
                System.out.print(arr[i] + " ");
            }
            System.out.println();
        }
    
        // for test
        public static void main(String[] args) {
    
            // 默认小根堆
            PriorityQueue<Integer> heap = new PriorityQueue<>();
            heap.add(6);
            heap.add(8);
            heap.add(0);
            heap.add(2);
            heap.add(9);
            heap.add(1);
    
            while (!heap.isEmpty()) {
                System.out.println(heap.poll());
            }
    
            int testTime = 500000;
            int maxSize = 100;
            int maxValue = 100;
            boolean succeed = true;
            for (int i = 0; i < testTime; i++) {
                int[] arr1 = generateRandomArray(maxSize, maxValue);
                int[] arr2 = copyArray(arr1);
                heapSort(arr1);
                comparator(arr2);
                if (!isEqual(arr1, arr2)) {
                    succeed = false;
                    break;
                }
            }
            System.out.println(succeed ? "Nice!" : "Fucking fucked!");
    
            int[] arr = generateRandomArray(maxSize, maxValue);
            printArray(arr);
            heapSort(arr);
            printArray(arr);
        }
    }

### 三、限定条件下堆排序：假设每个元素移动的距离一定不超过k，并且k相对于数组长度来说是比较小的 ###

> ***题意：***  
> *已知一个几乎有序的数组。几乎有序是指，如果把数组排好顺序的话，每个元素移动的距离一定不超过k，并且k相对于数组长度来说是比较小的。 请选择一个合适的排序策略，对这个数组进行排序。*  
>   
>  ***思路：***  
> *小根堆排序、优先队列：题目中提到了一个，每个元素移动的距离一定不超过k，那么就说明，从第一个数开始，前k+1个数里面，存在一个数，是一定要排在0位置的，这样才能使得移动不超过k个， 比如一个数组最小是1，长度为8，k=5，最小1是需要排在索引0位置的，为了满足移动不超过5个位置，那么在arr\[0-k\]区间内必然有1，最远只能在rr\[k\],那么也是移动k为来到0 k-k=0 ,利用这个特性，* *用小根堆，先把前k个数\[0,k-1\]入堆* *，* *然后第二次开始，从\[k,arr.length-1\]入堆，入一次 就依次从头赋值给原数组，然后再出堆* *；比如前面例子，第一次肯定是把1赋值给arr\[0\],出堆，往后入堆，赋值arr\[1\]，出堆..直到最后一个元素，* *最后可能堆还有元素，就依次赋值给后面的数组位置，依次出堆，完成堆排序*

**代码演示：（这里不手写堆结构，一般都是直接用PriorityQueue优先队列，默认小根堆排序，说是优先队列，其实也是堆结构实现的）**

package class06;
    
    import java.util.Arrays;
    import java.util.PriorityQueue;
    
    /**题意：
     * 已知一个几乎有序的数组。几乎有序是指，如果把数组排好顺序的话，每个元素移动的距离一定不超过k，并且k相对于数组长度来说是比较小的。
     * 请选择一个合适的排序策略，对这个数组进行排序。
     *
     * 思路：小根堆排序、优先队列：题目中提到了一个，每个元素移动的距离一定不超过k，那么就说明，从第一个数开始，前k+1个数里面，存在一个数，是一定要排在0位置的
     * 这样才能使得移动不超过k个， 比如一个数组最小是1，长度为8，k=5，最小1是需要排在索引0位置的，为了满足移动不超过5个位置，那么在arr[0-k]
     * 区间内必然有1，最远只能在rr[k],那么也是移动k为来到0 k-k=0 ,利用这个特性，用小根堆，先把前k个数[0,k-1]入堆，然后第二次开始，从[k,arr.length-1]
     * 入堆，入一次 就依次从头赋值给原数组，然后再出堆；比如前面例子，第一次肯定是把1赋值给arr[0],出堆，往后入堆，赋值arr[1]，出堆..直到最后一个元素，
     * 最后可能堆还有元素，就依次赋值给后面的数组位置，依次出堆，完成堆排序
     */
    public class SortArrayDistanceLessK {
        public static void sortArrayDistanceLessK(int[] arr, int k){
            if(arr == null || arr.length <2) return;
            PriorityQueue<Integer> heap = new PriorityQueue<>();
            //技巧：把堆索引定义外面，定义for里面的话就没法给，后续的操作使用
            int index = 0;
            //1.首先我们把0,k-1的区间先入堆，下次开始入k时，就时要开始循环赋值、出堆，因为arr[k] 前面有k个数，
            //题目限定每个元素移动不超过k ，那么排在arr[0]的数，肯定就是再0，k区间内，所以再k入堆时，就可以出堆，其
            //最小值就是位于arr[0]
            //判断最小值是因为我们测试用例的k范围是随机的可能会大于数组长度
            for(;index < Math.min(arr.length-1,k);index++){
                heap.add(arr[index]);
            }
            //2.此时index = k ,开始往后遍历,index不超过数组长度 赋值，出堆
            //定义数组从0开始的下标 用于赋值
            int indexArr = 0;
            for(;index<arr.length;index++,indexArr++){
                heap.add(arr[index]);
                //出堆，赋值，出堆是因为该值已经赋值到数组了，就需要排除
                arr[indexArr] = heap.poll();
            }
            //3.此时遍历到最后，堆可能还有元素，需要依次再赋值到arr[indexArr]位置
            while(!heap.isEmpty()){
                arr[indexArr++] = heap.poll();
            }
        }
    
        // for test
        public static void comparator(int[] arr, int k) {
            Arrays.sort(arr);
        }
    
        // for test
        public static int[] randomArrayNoMoveMoreK(int maxSize, int maxValue, int K) {
            int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
            for (int i = 0; i < arr.length; i++) {
                arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
            }
            // 先排个序
            Arrays.sort(arr);
            // 然后开始随意交换，但是保证每个数距离不超过K
            // swap[i] == true, 表示i位置已经参与过交换
            // swap[i] == false, 表示i位置没有参与过交换
            boolean[] isSwap = new boolean[arr.length];
            for (int i = 0; i < arr.length; i++) {
                int j = Math.min(i + (int) (Math.random() * (K + 1)), arr.length - 1);
                if (!isSwap[i] && !isSwap[j]) {
                    isSwap[i] = true;
                    isSwap[j] = true;
                    int tmp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = tmp;
                }
            }
            return arr;
        }
    
        // for test
        public static int[] copyArray(int[] arr) {
            if (arr == null) {
                return null;
            }
            int[] res = new int[arr.length];
            for (int i = 0; i < arr.length; i++) {
                res[i] = arr[i];
            }
            return res;
        }
    
        // for test
        public static boolean isEqual(int[] arr1, int[] arr2) {
            if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
                return false;
            }
            if (arr1 == null && arr2 == null) {
                return true;
            }
            if (arr1.length != arr2.length) {
                return false;
            }
            for (int i = 0; i < arr1.length; i++) {
                if (arr1[i] != arr2[i]) {
                    return false;
                }
            }
            return true;
        }
    
        // for test
        public static void printArray(int[] arr) {
            if (arr == null) {
                return;
            }
            for (int i = 0; i < arr.length; i++) {
                System.out.print(arr[i] + " ");
            }
            System.out.println();
        }
    
        // for test
        public static void main(String[] args) {
            System.out.println("test begin");
            int testTime = 500000;
            int maxSize = 100;
            int maxValue = 100;
            boolean succeed = true;
            for (int i = 0; i < testTime; i++) {
                int k = (int) (Math.random() * maxSize) + 1;
                int[] arr = randomArrayNoMoveMoreK(maxSize, maxValue, k);
                int[] arr1 = copyArray(arr);
                int[] arr2 = copyArray(arr);
                sortArrayDistanceLessK(arr1, k);
                comparator(arr2, k);
                if (!isEqual(arr1, arr2)) {
                    succeed = false;
                    System.out.println("K : " + k);
                    printArray(arr);
                    printArray(arr1);
                    printArray(arr2);
                    break;
                }
            }
            System.out.println(succeed ? "Nice!" : "Fucking fucked!");
        }
    
    }

### 四、最大线段重合问题（用堆的实现） ###

> **题意：**  
> 给定很多线段，每个线段都有两个数\[start, end\]，  
> 表示线段开始位置和结束位置，左右都是闭区间  
> 规定：  
> 1）线段的开始和结束位置一定都是整数值  
> 2）线段重合区域的长度必须>=1  
> 返回线段最多重合区域中，包含了几条线段  
>   
> ***思路：***  
> *1.先将原二维数组，按arr\[i\]\[0\] 起点位置进行升序排序*  
> *2.然后创建一个小根堆，遍历线段数组，如果堆内非空并且元素小于等于线段数组起点arr\[i\]\[0\]，就将元素出堆*  
> *3.最后将当前线段数组的终点arr\[i\]\[1\]入堆，当前堆大小表示当前线段数组起点arr\[i\]\[0\]有重叠的线段段数*  
> *4.依次比较每次的重叠线段数 刷新最大值，最后返回该最大值即为题目求的最大线段重合数*

package class07;
    
    import java.util.Arrays;
    import java.util.Comparator;
    import java.util.PriorityQueue;
    
    /**题意：
     * 最大线段重合问题（用堆的实现）
     * 给定很多线段，每个线段都有两个数[start, end]，
     * 表示线段开始位置和结束位置，左右都是闭区间
     * 规定：
     * 1）线段的开始和结束位置一定都是整数值
     * 2）线段重合区域的长度必须>=1
     * 返回线段最多重合区域中，包含了几条线段
     * 比如[1,3] [2,5],[2,8]这里三段都是重合，所以[2,5]重叠区间，结果为3  [1,3] [3,5] 这里没有重叠，只是边界重叠，重叠要保证是长度大于0的 结果为0
     *
     * 思路：
     * 1.先将原二维数组，按arr[i][0] 起点位置进行升序排序
     * 2.然后创建一个小根堆，遍历线段数组，如果堆内非空并且元素小于等于线段数组起点arr[i][0]，就将元素出堆
     * 3.最后将当前线段数组的终点arr[i][1]入堆，当前堆大小表示当前线段数组起点arr[i][0]有重叠的线段段数
     * 4.依次比较每次的重叠线段数 刷新最大值，最后返回该最大值即为题目求的最大线段重合数
     */
    
    public class CoverMax {
        //用于验证，不推荐该写法
        public static int maxCover1(int[][] lines) {
            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]);
            }
            int cover = 0;
            //为什么是加0.5 用小数来累加1是因为这里线段都是整数边界，需要判断是否有重叠，重叠区间某个数，无法确定整数，因为整数也可能是
            //边界重叠，但没有长度，而设一个小数，不管是零点几，都可以，只要重叠了，那么这区间肯定是有个小数的。所以就用每个小数累加1判断
            //从最小边界到最大边界， 看每个小数在整个区间的线段内有多少个重叠，标记保存到cover，循环下一个小数看看有多少个重叠,与cover保存
            //的值比较大小，更新重叠最大值
            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;
        }
    
        //定义一个类结构保存每个线段的起点终点
        public static class Line{
            public int start;
            public int end;
            public Line(int s,int e){
                start = s;
                end = e;
            }}
        public static int maxCover2(int[][] arr){
            //创建保存线段起止点的类数组,长度自然就是二维数组的长度 有多少对
            Line[] lines = new Line[arr.length];
            for(int i = 0; i< arr.length;i++){
                lines[i] = new Line(arr[i][0],arr[i][1]);
            }
            //对该对象数组，按start起点升序排序,相当于固定起点顺序 从小开始，排序之后，
            //从起点小的开始才能确保每段是否存在重叠
            Arrays.sort(lines,(a,b)->(a.start-b.start));
            //定义一个结果值 ，保存最大重叠的段数 小根堆，保存的是每段的终点值，小的排顶部。堆的大小就是表示每次的线段起点重叠的线段数
            int ans = 0;
            PriorityQueue<Integer> heap = new PriorityQueue<>();
            //开始遍历排好序的线段组，
            for(int i = 0;i<lines.length;i++){
                //先要判断当前堆是否空，如果不为空，并且存在有比当前起点小于等于的元素，元素即保存的是
                //其前面起点比当前小或等于的线段的终点， 那么就要弹出，因为前面的线段终点小于等于当前线段
                //起点，说明没有重叠长度，即使相等，也不符合题意要求，需要长度大于0，相交则为0,大于起点值，
                //说明有几个元素，就是表示前面有几段线段与当前段重叠
                while(!heap.isEmpty() && heap.peek() <= lines[i].start){
                    heap.poll();
                }
                //接着将当前段的终点入堆。
                heap.add(lines[i].end);
                //将定义的最大值变量，遍历与每次堆的长度比较大小，长度即表示当前段位起点有多少线段是重叠的。
                ans = Math.max(ans,heap.size());
            }
            return ans;
        }
    
        //不用类数组保存线段的写法，精简，推荐改写法
        public static int maxCover3(int[][] arr){
            //直接将当前二维数组进行排序，按元素的第一个索引元素排，也就是线段的起点升序
            Arrays.sort(arr,(a,b)->{
                return a[0]-b[0];
            });
            //定义小根堆，保存线段的终点值，堆内有多少个元素，就表示当前线段起点开始有多少个重合线段
            PriorityQueue<Integer> heap = new PriorityQueue<>();
            int ans = 0;
            //遍历排序好的线段
            for(int[] line:arr){
                //判断如果堆不为空，且堆有小于等于该线段起点的元素，就一直弹出，因为那些没有重叠
                while(!heap.isEmpty() && heap.peek() <= line[0]){
                    heap.poll();
                }
                //终点入堆
                heap.add(line[1]);
                //更新重叠的最大线段数，堆大小就表示当前以该线段起点有多少个线段重叠
                ans = Math.max(ans,heap.size());
            }
            return ans;
        }
    
        // 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<Line> {
    
            @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<Line> 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);
                int ans3 = maxCover3(lines);
                if (ans1 != ans2 || ans1 != ans3) {
                    System.out.println("Oops!");
                }
            }
            System.out.println("test end");
        }
    
    
    
    
    }