2.比较器
比较器：
1)比较器的实质就是重载比较运算符；
2)比较器可以很好的应用在特殊标准的排序上；
3)比较器可以很好的应用在根据特殊标准排序的结构上；
4)写代码变得异常容易，还用于范型编程。
先实现应用在特殊标准的排序，如下：
package heap04; import java.util.ArrayList; import java.util.Arrays; import java.util.Comparator; import java.util.TreeMap; /** * @author Corley * @date 2021/10/13 17:22 * @description LeetCodeAlgorithmZuo-heap04 */ public class CustomComparator { static class Student { private final String name; private final int id; private final 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 + '}'; } } /* * id升序比较器 * */ static class IdAscendingComparator implements Comparator<Student> { @Override public int compare(Student o1, Student o2) { return o1.id - o2.id; } } /* * 年龄降序比较器 * */ static class AgeDescendingComparator implements Comparator<Student> { @Override public int compare(Student o1, Student o2) { return o2.age - o1.age; } } /* * 复杂比较器，年龄降序、id升序 * */ static class AgeDescendingIdAscedingComparator implements Comparator<Student> { @Override public int compare(Student o1, Student o2) { return o1.age != o2.age ? o2.age - o1.age : o1.id - o2.id; } } public static void main(String[] args) { Student student1 = new Student("A", 3, 40); Student student2 = new Student("B", 2, 21); Student student3 = new Student("C", 4, 12); Student student4 = new Student("D", 5, 62); Student student5 = new Student("E", 3, 42); Student[] studentArray = new Student[] {student1, student2, student3, student4, student5}; Arrays.sort(studentArray, new IdAscendingComparator()); System.out.println(Arrays.toString(studentArray)); System.out.println("-------------------------------------"); ArrayList<Student> studentList = new ArrayList<>(); studentList.add(student1); studentList.add(student2); studentList.add(student3); studentList.add(student4); studentList.add(student5); studentList.sort(new AgeDescendingComparator()); System.out.println(studentList); System.out.println("-------------------------------------"); TreeMap<Student, String> studentMap = new TreeMap<>(new AgeDescendingIdAscedingComparator()); studentMap.put(student1, "我是学生1，我的名字叫A"); studentMap.put(student2, "我是学生2，我的名字叫B"); studentMap.put(student3, "我是学生3，我的名字叫C"); studentMap.put(student4, "我是学生4，我的名字叫D"); studentMap.put(student5, "我是学生5，我的名字叫E"); System.out.println(studentMap.keySet()); } }
输出：
[Student{name='B', id=2, age=21}, Student{name='A', id=3, age=40}, Student{name='E', id=3, age=42}, Student{name='C', id=4, age=12}, Student{name='D', id=5, age=62}] ------------------------------------- [Student{name='D', id=5, age=62}, Student{name='E', id=3, age=42}, Student{name='A', id=3, age=40}, Student{name='B', id=2, age=21}, Student{name='C', id=4, age=12}] ------------------------------------- [Student{name='D', id=5, age=62}, Student{name='E', id=3, age=42}, Student{name='A', id=3, age=40}, Student{name='B', id=2, age=21}, Student{name='C', id=4, age=12}]
再实现应用在根据特殊标准排序的结构，如下：
package heap04; import java.util.Comparator; import java.util.PriorityQueue; /** * @author Corley * @date 2021/10/13 14:56 * @description LeetCodeAlgorithmZuo-heap04 */ public class HeapUse { /* * 整型比较器 * */ static class IntegerComparator 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<>(); // 大根堆 PriorityQueue<Integer> heap = new PriorityQueue<>(new IntegerComparator()); heap.add(5); heap.add(7); heap.add(3); heap.add(0); heap.add(5); heap.add(2); while (!heap.isEmpty()) { System.out.println(heap.poll()); } } }
可以看到，用PriorityQueue实现了大根堆。
语言提供的堆结构vs手写的堆结构：
取决于有没有动态改信息的需求；
语言提供的堆结构，如果你动态改数据，不保证依然有序；
手写堆结构，因为增加了对象的位置表，所以能够满足动态改信息的需求。
思路如下：
实现如下：
package heap04; import java.util.ArrayList; import java.util.Comparator; import java.util.HashMap; import java.util.PriorityQueue; /** * @author Corley * @date 2021/10/13 19:24 * @description LeetCodeAlgorithmZuo-heap04 */ public class CustomHeap { static class SelfHeap<T> { private final ArrayList<T> heap; // 小根堆 private final HashMap<T, Integer> indexMap; private int heapSize; private final Comparator<? super T> comparator; public SelfHeap(Comparator<? super T> comparator) { heap = new ArrayList<>(); indexMap = new HashMap<>(); heapSize = 0; this.comparator = comparator; } public boolean isEmpty() { return heapSize == 0; } public int size() { return heapSize; } public boolean contains(T key) { return indexMap.containsKey(key); } public void push(T value) { heap.add(value); indexMap.put(value, heapSize); heapInsert(heapSize++); } public T pop() { T ans = heap.get(0); int end = heapSize - 1; swap(0, end); heap.remove(end); indexMap.remove(ans); heapify(0, --heapSize); return ans; } public void resign(T value) { int valueIndex = indexMap.get(value); heapInsert(valueIndex); heapify(valueIndex, heapSize); } private void heapInsert(int index) { while (comparator.compare(heap.get(index), heap.get((index - 1) / 2)) < 0) { swap(index, (index - 1) / 2); index = (index - 1) / 2; } } private void heapify(int index, int heapSize) { int left = index * 2 + 1; while (left < heapSize) { int smallest = left + 1 < heapSize && (comparator.compare(heap.get(left + 1), heap.get(left)) < 0) ? left + 1 : left; smallest = comparator.compare(heap.get(smallest), heap.get(index)) < 0 ? smallest : index; if (smallest == index) { break; } swap(smallest, index); index = smallest; left = index * 2 + 1; } } private void swap(int i, int j) { T t1 = heap.get(i); T t2 = heap.get(j); heap.set(i, t2); heap.set(j, t1); indexMap.put(t1, j); indexMap.put(t2, i); } } public static class Student { public int classNo; public int age; public int id; public Student(int c, int a, int i) { classNo = c; age = a; id = i; } } public static class StudentComparator implements Comparator<Student> { @Override public int compare(Student o1, Student o2) { return o1.age - o2.age; } } public static void main(String[] args) { Student s1 = new Student(2, 50, 11111); Student s2 = new Student(1, 60, 22222); Student s3 = new Student(6, 10, 33333); Student s4 = new Student(3, 20, 44444); Student s5 = new Student(7, 72, 55555); Student s6 = new Student(1, 14, 66666); SelfHeap<Student> myHeap = new SelfHeap<>(new StudentComparator()); myHeap.push(s1); myHeap.push(s2); myHeap.push(s3); myHeap.push(s4); myHeap.push(s5); myHeap.push(s6); while (!myHeap.isEmpty()) { Student cur = myHeap.pop(); System.out.println(cur.classNo + "," + cur.age + "," + cur.id); } } }
之所以这种方式可以实现修改其中的元素后能重新排序，一个重要的原因是因为存入堆中的其实只是元素的引用，在修改元素的属性之后，引用对应的堆区对象的属性就会发生改变，所以相当于堆中的某个元素的属性发生变化，此时如果以这个属性为排序依据，则需要调用heapInsert和heapify方法对堆进行调整，以满足大根堆或小根堆的条件。
在实际使用中，选择堆时，如果只是单纯向堆中加入或取元素，则可以直接使用系统提供的堆；
如果需要对堆中的元素进行修改，则需要自己实现堆和对应的比较器。
总结
堆是在完全二叉树的基础上实现的，分为大根堆和小根堆，堆排序实现了O(N*LogN)的时间复杂度。比较器可以很好的应用在特殊标准的排序和根据特殊标准排序的结构上。
