1.java中的比较器

Java 中主要有两种形式的比较器：Comparable 和 Comparator。

1.1 Comparable（内部比较器）

Comparable 接口用于定义类的自然排序。只有一个方法 compareTo()。

实现形式： 你需要在需要排序的类（比如 Person 类）中实现 Comparable 接口，并重写 compareTo() 方法。

代码示例：

public class Person implements Comparable<Person> {
    private String name;
    private int age;

    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }

    public String getName() {
        return name;
    }

    public int getAge() {
        return age;
    }

    @Override
    public int compareTo(Person other) {
        // 根据年龄进行升序排序
        return this.age - other.age;
    }

    @Override
    public String toString() {
        return "Person{" +
               "name='" + name + '\'' +
               ", age=" + age +
               '}';
    }
}

特点：

侵入性强： 需要修改被排序的类本身的代码。
单一性： 一个类只能有一个自然排序，即只能实现一个 compareTo() 方法。
应用场景： 当你想为某个类定义一个默认的、最常见的排序规则时使用。

1.2. Comparator（外部比较器）

Comparator 接口用于定义自定义排序。它位于 java.util 包中，常用于对那些没有实现 Comparable 接口的类，或者需要多种排序方式的场景。

实现形式： 你可以创建一个独立的类来实现 Comparator 接口，或者使用匿名内部类、Lambda 表达式来创建比较器实例。

如下方法： @Override public int compare(T o1, T o2) ; 返回负数的情况，就是o1比o2优先的情况 返回正数的情况，就是o2比o1优先的情况 返回0的情况，就是o1与o2同样优先的情况

独立的比较器类：

import java.util.Comparator;
  
public class PersonNameComparator implements Comparator<Person> {
    @Override
    public int compare(Person p1, Person p2) {
        // 根据姓名进行升序排序
        return p1.getName().compareTo(p2.getName());
    }
}

Lambda 表达式（推荐）：

import java.util.Comparator;
  
// 根据姓名进行升序排序
Comparator<Person> nameComparator = (p1, p2) -> p1.getName().compareTo(p2.getName());

特点：

侵入性弱： 不需要修改被排序的类，是一种“即插即用”的排序方式。
多样性： 一个类可以有多种排序方式，比如你可以创建按姓名排序的 Comparator，也可以创建按年龄降序排序的 Comparator。
应用场景：
- 需要对不可修改的类进行排序（如 JDK 自带的类）。
- 需要为同一个类提供多种排序规则时。

1.3 总结与对比

特性	Comparable (内部比较器)	Comparator (外部比较器)
接口位置	`java.lang`	`java.util`
使用方式	在类内部实现	在类外部实现
方法	`compareTo(Object obj)`	`compare(Object o1, Object o2)`
侵入性	强（修改被排序的类）	弱（不需要修改被排序的类）
排序规则	只能定义一个自然排序	可以定义多个自定义排序
应用场景	为类定义默认排序	需要多种排序方式，或对不可修改的类排序

在 Java 8 之后，Comparator 接口引入了许多便捷的静态方法（如 comparing()、reversed()），这使得使用 Lambda 表达式创建比较器变得非常简单和优雅。因此，在现代 Java 开发中，Comparator 尤其是结合 Lambda 表达式的方式，被更广泛地使用。

2.堆结构

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

heapInsert和heapify操作

参考博客：https://kirsten-1.github.io/2025/04/05/%E7%AE%97%E6%B3%95025/

heapInsert和heapify的操作的时间复杂度：O(logN)

语言提供的堆结构 vs 手写的堆结构

取决于，你有没有动态改信息的需求！
语言提供的堆结构，如果你动态改数据，不保证依然有序
手写堆结构，因为增加了对象的位置表，所以能够满足动态改信息的需求

3.堆排序

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

堆排序代码参考博客：https://kirsten-1.github.io/2025/04/05/%E7%AE%97%E6%B3%95025/

4.题目-几乎有序

已知一个几乎有序的数组。几乎有序是指，如果把数组排好顺序的话，每个元素移动的距离一定不超过k，并且k相对于数组长度来说是比较小的。

请选择一个合适的排序策略，对这个数组进行排序。

思路整理如下：

使用小顶堆来解决该问题，它要使移动元素不超过k，那么就要将k+1个元素放入小顶堆。
将堆顶元素弹出放入数组对应的位置，比如第一次弹出的一定是最小的，(由小顶堆的性质可知，根节点一定小于左右节点的，但是左右节点大小就不一定类。) 然后为了保持堆的大小不变(主要是由于k的限制，所以堆的长度只能为k+1)，第一个元素已经确定好了，故可以不用考虑，然后将第k+2个元素入堆，进行小根堆调整，保证满足小根堆条件。
当数组元素长度已经不满足k+1时，直接将heap中剩下的元素给拷贝到数组就行。

时间复杂度是O(Nlogk),额外空间复杂度是O(k+1)

试题链接：https://kirsten-1.github.io/2025/09/22/%E7%AE%97%E6%B3%95%E9%A2%98%E5%BA%93-1%E5%87%A0%E4%B9%8E%E6%9C%89%E5%BA%8F/

解法：

public static void sortedArrDistanceLessK(int[] arr, int k) {
    if (k == 0) {
        return;
    }
    int N = arr.length;
    int index = 0;
    PriorityQueue<Integer> heap = new PriorityQueue<>();
    for (; index <= Math.min(N - 1, k - 1); index++) {
        heap.add(arr[index]);
    }
    int i = 0;
    for (; index < N; i++, index++) {
        heap.add(arr[index]);
        arr[i] = heap.poll();
    }
    while (!heap.isEmpty()) {
        arr[i++] = heap.poll();
    }
}

【体系学习006】堆结构和堆排序