• 堆排序 — — 堆结构及问题【十大经典排序算法】

    1 堆结构

    1.1 相关概念

    • 堆结构就是用数组实现的完全二叉树
    • 大根堆：每棵子树的最大值都在顶部
    • 小根堆：每课子树的最小值都在顶部
    • 堆结构的heapInsert（上升）与heapify（下沉）操作
    • 堆结构的增大和减小
    • 优先级队列就是堆结构（PriorityQueue）

    1.2 实现堆结构

    全部代码：

    public static class MyMaxHeap2{
      //数组：用于存放堆数据
      private int[] heap;
      //用于指定数组大小
      private final int limit;
      //用于标记堆大小
      private int heapSize;

      public MyMaxHeap2(int limit){
          heap = new int[limit];
          this.limit = limit;
          //初始堆大小为0
          heapSize = 0;
      }

      //判断堆是否为空
      public boolean isEmpty(){
          return heapSize == 0;
      }

      //判断是否将数组所有元素都存入堆中了【是否满了】
      public boolean isFull(){
          return limit == heapSize;
      }

      //将元素放入堆中
      public void push(int val){
          //堆中元素已满
          if(heapSize == limit){
              throw new RuntimeException("heap is full");
          }
          heap[heapSize] = val;
          heapInsert(heap, heapSize++);
      }

      //pop
      //返回最大值，并且在大根堆中，将最大值删掉【逻辑删除】
      //剩下的数，依然保持大根堆结构
      public int pop(){
          //0位置为最大值【大根堆】
          int ans = heap[0];
          //让0位置与数组最后一个位置交换
          swap(heap, 0, --heapSize);
          heapify(heap, 0, heapSize);
          return ans;
      }

      //上浮
      //新加进来的数，现在停在了index位置 -> 上浮
      //移动到0位置或干不掉自己的父亲节点了，停
      private void heapInsert(int[] arr, int index){
          //大于自己的父亲，交换
          while(arr[index] > arr[(index - 1) / 2]){
              swap(heap, index, (index - 1) / 2);
              //来到自己父亲的位置
              index = (index - 1) / 2;
          }
      }

      //下沉
      //从index位置往下看，不断地下沉
      //停：较大的孩子不再比index位置的数大；或已经没孩子了
      private void heapify(int[]  arr, int index, int heapSize){
          //左孩子位置
          int left = index * 2 + 1;
          while(left < heapSize){//如果有左孩子；有没有右孩子，可能没有
              //把较大孩子的下标给largest
              //left：index下面的左孩子
              //left+1：右孩子
              int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;
              //将孩子节点的最大值与index的值比较，看谁大
              largest = arr[largest] > arr[index] ? largest : index;
              if(largest == index){
                  //index的值大,不用交换，直接返回
                  break;
              }
              //将index与较大孩子交换
              swap(arr, largest, index);
              //继续下沉
              index = largest;
              left = index * 2 + 1;
          }
      }

      public void swap(int[] arr, int i, int j){
          int temp = arr[i];
          arr[i] = arr[j];
          arr[j] = temp;
      }
  }

    • 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
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90

    1.3 拓展

    我们也可以使用Java内部自带的优先级队列来实现堆结构（默认小跟堆），如果想要创建大根堆，我们可以通过自定义比较器来实现（O2 - O1）
    代码：

    
//自定义比较器，实现大根堆
    public static class MyComparator1 implements Comparator<Integer> {

        @Override
        public int compare(Integer o1, Integer o2) {
            //- (o1 - o2)
            return o2 - o1;
        }
    }

    public static void main(String[] args) {
        //默认小跟堆
        PriorityQueue<Integer> heap1 = new PriorityQueue<>();
        heap1.add(2);
        heap1.add(9);
        heap1.add(1);
        heap1.add(-2);
        while(!heap1.isEmpty()){
            System.out.print(heap1.poll() + " ");
        }
        System.out.println();
        //创建自定义比较器【大的放在前】
        MyComparator1 myComparator1 = new MyComparator1();
        PriorityQueue<Integer> heap2 = new PriorityQueue<>(myComparator1);
        heap2.add(4);
        heap2.add(1);
        heap2.add(-4);
        heap2.add(7);
        heap2.add(8);
        while(!heap2.isEmpty()){
            System.out.print(heap2.poll() + " ");
        }
        //8 7 4 1 -4
        System.out.println();
}

    • 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

    2 堆排序

    1. 先让整个数组都变成大根堆，建立堆的过程：
      1）从上到下：O（N*logN）
      2）从下到上：O（N）
    2. 把堆的最大值与堆末尾的值（数组末尾）交换，然后减小堆的大小（heapSize）之后，再去调整堆，周而复始，时间复杂度为O（N*logN）【每次选出最大的】
    3. 堆的大小减少到0之后，排序完成

    2.1 heapInsert(int[] arr, int index) 上浮

    堆排序，上浮功能实现

    /**
  * 上浮 ：只用传入index下标即可，因为是往上走，不会越界
  * @param arr
  * @param index
  */
 public static void heapInsert(int[] arr, int index){
     while(arr[index] > arr[(index - 1) / 2]){
         swap(arr, index, (index - 1) / 2);
         index = (index - 1) / 2;
     }
 }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    2.2 heapify(int[] arr, int index, int heapSize) 下沉

    /**
 *  下沉:传入arr数组【堆结构】及heapSize（堆元素个数）
 * @param arr
 * @param index
 * @param heapSize
 */
public static void heapify(int[] arr, int index, int heapSize){
    int left = index * 2 + 1;//左孩子下标
    while(left < heapSize){//下方还有孩子【为什么是用left比较呢？是因为默认以完全二叉树来排列】
        //两个孩子谁大，谁把下标值给largest
        //1)只有左孩子， left -> largest
        //2)同时有左孩子和右孩子， 右孩子的值 <= 左孩子的值， left -> largest
        //同时有左孩子和右孩子，右孩子的值 > 左孩子， right -> largest
        int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;
        //父和较大孩子之前，谁的值大，谁就把下标给largest
        largest = arr[largest] > arr[index] ? largest : index;
        if (largest == index) {
            break;
        }
        swap(arr, largest, index);
        index = largest;
        left = index * 2 + 1;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24

    2.3 swap(int[] arr, int i, int j) 交换

    public static void swap(int[] arr, int i, int j) {
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

    • 1
    • 2
    • 3
    • 4
    • 5

    2.4 heapSort(int[] arr) 核心逻辑

    首先，将数组中的数全部下沉，进行堆结构，然后再交换首末位置，每次找出最大值，最后再上浮

    //堆排序
public static void heapSort(int[] arr){
    if(arr == null || arr.length < 2){
        return;
    }
    //第一种方法：
    //O(N)
    for(int i = arr.length - 1; i >= 0; i--){
        //下沉
        heapify(arr, i, arr.length);
    }
    //第二种
   	// O(N*logN)
	//for (int i = 0; i < arr.length; i++) { // O(N)
	//	heapInsert(arr, i); // O(logN)
	//}
    int heapSize = arr.length;
    swap(arr, 0, --heapSize);
    //O(N*logN)
    while(heapSize > 0){//O(N)
        heapify(arr, 0, heapSize);
        swap(arr, 0, --heapSize);//每次找到最大
    }

}

    • 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

    具体实现逻辑中：
    ①下沉 - 交换 - 上浮 【O(N)】:提前知道所有数组(堆)的组成元素
    ②上浮 - 交换 - 上浮 【O(N*logN)】

    3 相关算法题

    3.1 最大线段重合问题

    给定很多线段，每个线段都有两个数[start, end],表示线段开始和结束为止
    规定：
    1）线段的开始和结束位置都是整数值
    2）线段重合区域长度必须>=1

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

    3.1.1 创建内部类，用来表示每条线段

    //定义内部类用来表示线段
public static class Line{
    private int start;
    private int end;

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    3.1.2 自定义比较器，按照线段的起始点排序

    //自定义比较器，将数组按照start大小排序
public static class MyComparator implements Comparator<Line>{

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    3.1.3 主要逻辑【小根堆】

    创建小根堆，每次将line.start与堆顶元素比较

    public static int maxCover2(int[][] m){
    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, new MyComparator());
    //创建小根堆【优先级队列，默认小根堆】
    PriorityQueue<Integer> heap = new PriorityQueue<>();
    int res = 0;
    for(int i = 0; i < lines.length; i++){
        //堆不为空 同时 堆顶元素 <= line.start【小于等于起始：刚好在范围外】
        // |__|__|
        //       |____|
        while(!heap.isEmpty() &&  heap.peek() <= lines[i].start){
            //出堆
            heap.poll();
        }
        //将新Line的end加入堆
        heap.add(lines[i].end);
        res = Math.max(res, heap.size());//每次与堆中元素个数比较，保留最大值
    }
    return res;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24

    3.1.4 全部代码

        //定义内部类用来表示线段
    public static class Line{
        private int start;
        private int end;

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

    //自定义比较器，将数组按照start大小排序
    public static class MyComparator implements Comparator<Line>{

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

    public static int maxCover2(int[][] m){
        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, new MyComparator());
        //创建小根堆【优先级队列，默认小根堆】
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        int res = 0;
        for(int i = 0; i < lines.length; i++){
            //堆不为空 同时 堆顶元素 <= line.start【小于等于起始：刚好在范围外】
            // |__|__|
            //       |____|
            while(!heap.isEmpty() &&  heap.peek() <= lines[i].start){
                //出堆
                heap.poll();
            }
            //将新Line的end加入堆
            heap.add(lines[i].end);
            res = Math.max(res, heap.size());//每次与堆中元素个数比较，保留最大值
        }
        return res;
    }

    • 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
  • 相关阅读:
    IDM激活
    JVM原理（GC，内存），JAVA底层
    《数据结构、算法与应用C++语言描述》-队列的应用-图元识别问题
    华测监测预警系统 2.2 存在任意文件读取漏洞
    ClickHouse 笔记1 | 简介、特点 | 基于CentOS7系统的安装与使用 | 常用数据类型 | MergeTree 表引擎 | SQL操作
    解析java中创建并运行线程的三种方式
    新能源汽车BMS控制器简介
    线程第一次启动和异常的注册（UEF的一个特性）
    行为型设计模式之中介者模式
    【Spring Boot Bean 注入详解】
  • 原文地址：https://blog.csdn.net/weixin_45565886/article/details/126268549