8、比较器、优先级队列

标签：优先级 Student 队列比较 int add heap new public

1、比较器 Comparator

所有的Comparator返回：
负数：认为第一个参数应放前面
正数：认为第二个参数应放前面
零：相等，那个放前面无所谓

1.定义与使用

实现Comparator接口重写方法 int compare(T o1, T o2);
public class StuIdComparator implements Comparator<T>
Arrays.sort(students, new StuIdComparator());
或者直接使用lambda表达式：
Arrays.sort(students, (a,b)-> a.id - b.id);

点击查看代码

public class Student {
    public String name;
    public int id;
    public int age;

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

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

public class ShowComparator {
    private static void printArray(int[] arr) {
        int len = arr.length;
        for (int i = 0; i < len; i++) {
            System.out.print(arr[i]);
        }
        System.out.println();
    }

    private static void printStudents(Student[] stus) {
        int len = stus.length;
        for (int i = 0; i < len; i++) {
            System.out.println(stus[i]);
        }
    }
    
    // 按id升序
    public static class StuIdComparator implements Comparator<Student> {
        @Override
        public int compare(Student o1, Student o2) {
            return o1.id - o2.id;
        }
    }

    public static void main(String[] args) {
        int[] arr = {3, 8, 1, 4, 9, 7, 5, 6, 2, 0};
        printArray(arr);
        Arrays.sort(arr);
        printArray(arr);

        Student s1 = new Student("张三", 5, 27);
        Student s2 = new Student("李四", 1, 17);
        Student s3 = new Student("王五", 4, 29);
        Student s4 = new Student("赵六", 3, 9);
        Student s5 = new Student("左七", 2, 34);
        Student[] students = {s1, s2, s3, s4, s5};

        printStudents(students);
        System.out.println("==[]==========");
        // 使用自定义比较器，定义2个对象怎么比较
        Arrays.sort(students, new StuIdComparator());
        printStudents(students);

        System.out.println("===ArrayList=====================");
        List<Student> stuList = new ArrayList<>();
        stuList.add(s1);
        stuList.add(s2);
        stuList.add(s3);
        stuList.add(s4);
        stuList.add(s5);
        // 按照加入顺序打印
        for (Student student : stuList) {
            System.out.println(student);
        }
        System.out.println("====================");
        // 按照自定义比较器排序
        stuList.sort(new StuIdComparator());
        for (Student student : stuList) {
            System.out.println(student);
        }
    }
}

2、优先级队列 PriorityQueue

优先级队列 PriorityQueue 默认是小根堆，自动按照升序排序，出队元素自然就是有序的

2.1、常用方法

方法	作用
add()	向队列中添加元素
peek()	查看头元素，不删除
poll()	出队，删除队列头元素并返回其值

2.2、简单代码如下

例如：加入【6，2，3，1，7】
peek()查看当前头部元素：1
加入：【0】
peek()查看当前头部元素：0

public static void priorityQueue() {
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        heap.add(6);
        heap.add(2);
        heap.add(3);
        heap.add(1);
        heap.add(7);
        // 会自动把最小的元素放到顶部
        System.out.println(heap.peek()); // 1
        heap.add(0);
        System.out.println(heap.peek()); // 0
        System.out.println("==================");
        // 按照从小到大的顺序弹出
        while (!heap.isEmpty()) {
            System.out.println(heap.poll());
        }
    }

输出：

2.3、自定义比较器，实现大根堆

PriorityQueue<Integer> heap = new PriorityQueue<>((a, b) -> b - a)；

例如：加入【6，2，3，1，7】
peek()查看当前头部元素：7
加入：【8】
peek()查看当前头部元素：8
输出：

2.4、只要是跟有序有关的结构，均可以自定义比较器

例如：TreeMap, TreeSet, PriorityQueue, List等

int[] arr = {2,1,3}
Arrays.sort(arr, new ArrComparator());
// list
List<T> list = new ArrayList<>();
list.sort(new TComparator());

2.5、合并K个有序链表

测试链接：https://leetcode.com/problems/merge-k-sorted-lists/
给定一个链表长度为k的链表数组，每个链表按升序排序。
将数组中所有的链表合并为一个有序的链表，并返回它。
示例：

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
  1->4->5,
  1->3->4,
  2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6

代码实现：