- [1 比较器与堆](#1) * [1.1 堆结构](#11) + [1.1.1 完全二叉树结构](#111) + [1.1.2 数组实现堆](#112) + [1.1.3 大根堆与小根堆](#113) + [1.1.4 构建堆](#114) + [1.1.5 堆排序](#115) + [1.1.6 语言、系统提供的堆和手写堆的选择](#116) - [1.1.6.1 系统实现的堆](#1161) - [1.1.6.2 系统堆和手写堆选择](#1162) * [1.2 比较器](#12)

1 比较器与堆

>

1.1 堆结构

>

1.1.1 完全二叉树结构

> > 完全二叉树结构：要么本层是满的，要么先满左边的，以下都是完全二叉树 1. ``` graph TD A-->B A-->C ``` 2. ``` graph TD A-->B A-->C B-->D B-->E C-->F ```

1.1.2 数组实现堆

> - 堆结构就是用数组实现的完全二叉树结构 > 用数组实现完全二叉树结构，从数组下标0开始，当成依次补齐二叉树结构的数据 ``` graph TD 0--> 1 0--> 2 1--> 3 1-->4 2-->5 2-->6 ``` 某位置i的左孩子下标为： ```math lchild = 2*i + 1 ``` 某位置i的右孩子的下标为： ```math rchild = 2*i + 2 ``` 某位置i的父节点位置为： ```math parent = (i-1) / 2 ``` > 当我们不使用数组的0下标，从1位置开始构建完全二叉树时，方便使用位操作： 某位置i的左孩子下标为： ```math lchild = 2*i <==> i << 1 ``` 某位置i的右孩子的下标为： ```math rchild = 2*i + 1 <==> (i << 1) | 1 ``` 某位置i的父节点位置为： ```math parent = i / 2 <==> i >> 1 ```

1.1.3 大根堆与小根堆

> - 完全二叉树中如果每棵子树的最大值都在顶部就是大根堆 - 完全二叉树中如果每颗子树的最小值都在顶部就是小根堆 ==我们认为堆就是大根堆或者小根堆，既不是大根堆也不是小根堆的完全二叉树只是完全二叉树，不能称之为堆==

1.1.4 构建堆

- 堆结构的heapInsert与heapify操作 heapInsert 思路：例如我们要构建一个大根堆，我们把所有的数依次添加到一个数组（下标从0开始）中去，每次添加一个数的时候，要去用找父亲节点的公式parent = (i-1) / 2找到父节点区比较，如果比父节点大就和父节点交换向上移动，移动后再用自己当前位置和父亲节点比较...，小于等于父节点不做处理。这样用户每加一个数，我们都能保证该结构是大根堆，对应代码的push方法 > 我们的调整代价实际上就是这颗树的高度层数，logN heapify > 原堆结构，删除最大值，继续调整维持成大根堆 思路：我们删除了最大值，也就是arr[0]位置，之后我们把堆最末尾的位置调整到arr[0]位置，堆大小减一。让现在arr[0]位置的数找左右孩子比较...，进行hearify操作，让其沉下去。沉到合适的位置之后，仍然是大根堆。对应代码的pop方法 > heapify的下沉操作，仍然是树的高度，logN > 堆结构很重要很重要 ```Java package class04; public class Code02_Heap01 { public static class MyMaxHeap { // 我们的大根堆 private int[] heap; private final int limit; // 表示目前这个堆收集了多少个数，也表示添加的下一个数应该放在哪个位置 private int heapSize; public MyMaxHeap(int limit) { heap = new int[limit]; this.limit = limit; heapSize = 0; } public boolean isEmpty() { return heapSize == 0; } public boolean isFull() { return heapSize == limit; } // 每加入一个数，需要动态维持堆结构 public void push(int value) { if (heapSize == limit) { throw new RuntimeException("heap is full"); } heap[heapSize] = value; // value heapSize heapInsert(heap, heapSize++); } // 用户此时，让你返回最大值，并且在大根堆中，把最大值删掉 // 剩下的数，依然保持大根堆组织 public int pop() { int ans = heap[0]; swap(heap, 0, --heapSize); heapify(heap, 0, heapSize); return ans; } // 往堆上添加数，需要用当前位置找父节点比较 private void heapInsert(int[] arr, int index) { // arr[index] // arr[index] 不比 arr[index父]大了 ， 停 // index = 0时也停 while (arr[index] > arr[(index - 1) / 2]) { swap(arr, index, (index - 1) / 2); index = (index - 1) / 2; } } // 从index位置，往下看，不断的下沉， // 停的条件：我的孩子都不再比我大；已经没孩子了 private void heapify(int[] arr, int index, int heapSize) { int left = index * 2 + 1; // 左孩子没越界，如果左孩子越界有孩子一定也越界 while (left < heapSize) { // 左右两个孩子中，谁大，谁把自己的下标给largest // 什么请款下选择右 -> (1) 有右孩子 && (2)右孩子的值比左孩子大才行 // 否则，左 int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left; // 左右孩子中最大值，和当前值比较，谁大谁把下标给largest(当前，左，右的最大值下标) largest = arr[largest] > arr[index] ? largest : index; // index位置上的数比左右孩子的数都大，已经无需下沉 if (largest == index) { break; } // 交换后，继续找左右孩子进行比较，周而复始 swap(arr, largest, index); index = largest; left = index * 2 + 1; } } private void swap(int[] arr, int i, int j) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } } // 暴力，O(N)复杂度实现的大根堆。用来做对数器 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 void main(String[] args) { 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.5 堆排序

> 1. 对于用户给的所有数据，我们先让其构建成为大根堆 2. 对于0到N-1位置的数，我们依次让N-1位置的数和0位置的数（全局最大值）交换,此时全局最大值来到了数组最大位置，堆大小减一，再heapify调整成大根堆。再用N-2位置的数和调整后的0位置的数交换，相同操作。直至0位置和0位置交换。每次heapify为logN，交换调整了N次 3. 所以堆排序的时间复杂度为O(NlogN) 4. 堆排序额为空间复杂度为O(1)，且不存在递归行为 ```Java package class04; import java.util.Arrays; import java.util.PriorityQueue; public class Code04_HeapSort { // 堆排序额外空间复杂度O(1) public static void heapSort(int[] arr) { if (arr == null || arr.length < 2) { return; } // O(N*logN),原始版本 // for (int i = 0; i < arr.length; i++) { // O(N) // heapInsert(arr, i); // O(logN) // } // 优化版本，heapInsert改为heapify。从末尾开始看是否需要heapify=》O(N)复杂度。 // 但是这只是优化了原有都是构建堆（O(NlogN)），最终的堆排序仍然是O(NlogN) for (int i = arr.length - 1; i >= 0; i--) { heapify(arr, i, arr.length); } int heapSize = arr.length; swap(arr, 0, --heapSize); // O(N*logN) while (heapSize > 0) { // O(N) heapify(arr, 0, heapSize); // O(logN) swap(arr, 0, --heapSize); // O(1) } } // arr[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; } } // arr[index]位置的数，能否往下移动 public static void heapify(int[] arr, int index, int heapSize) { // 左孩子的下标 int left = index * 2 + 1; // 下方还有孩子的时候 while (left < heapSize) { // 两个孩子中，谁的值大，把下标给largest // 1）只有左孩子，left -> largest // 2) 同时有左孩子和右孩子，右孩子的值<= 左孩子的值，left -> largest // 3) 同时有左孩子和右孩子并且右孩子的值> 左孩子的值， 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; } } public static void swap(int[] arr, int i, int j) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } // 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 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); } } ``` > 关于上述heapInsert改为heapIfy的优化： 在我们从0到N-1进行heapInsert的时候，是O(NlogN)不做解释，当我们从N-1到0上依次heapify的时候，整体来看，整棵树的跟节点的heapify层数N/2，第二层为N/4且有两个节点。那么实质是N个不同的层数相加： ```math T(N) = (\frac{N}{2} * 1) + (\frac{N}{4} * 2) + (\frac{N}{8} * 3) + (\frac{N}{16} * 4) + ... => 2T(N) = (\frac{N}{2} * 2) + (\frac{N}{2} * 2) + (\frac{N}{4} * 3) + (\frac{N}{8} * 4) + ... => T(N) = N + \frac{N}{2} + \frac{N}{4} + \frac{N}{8} + ... => O(N) ```

1.1.6 语言、系统提供的堆和手写堆的选择

>

1.1.6.1 系统实现的堆

> > 系统实现的堆实质上就是优先级队列，虽然名称叫优先级队列，底层就是堆实现的。默认是小根堆，我们可以自定义比较器把它改为大根堆 ```Java package class04; import java.util.Comparator; import java.util.PriorityQueue; public class Test { // 负数，o1 放在上面的情况 public static class MyComp implements Comparator{ @Override public int compare(Integer o1, Integer o2) { return o2 - o1; } } public static void main(String[] args) { System.out.println("hello"); // 大根堆 PriorityQueue heap = new PriorityQueue<>(new MyComp()); heap.add(5); heap.add(7); heap.add(3); heap.add(0); heap.add(2); heap.add(5); while(!heap.isEmpty()) { System.out.println(heap.poll()); } } } ``` 堆的相关面试题： 题目一：已知一个几乎有序的数组。几乎有序是指，如果把数组排好序的话，每个元素移动的距离一定不超过k，并且k相对于数组长度来说是比较小的。请选择一个合适的排序策略，对这个数组进行排序 > 思路：例如给定一个数组，k=5,那么我们从0开始，前K+1个数也就是0到5位置的数放到小根堆，排序之后把最小的放到0位置，接下来把6位置放小根堆(此时小根堆里面有0到6位置的数),由于0位置的数有距离限制只能从0到5上选择，所以此时弹出最小值放到1位置，此时1位置被固定... ```Java package class04; import java.util.Arrays; import java.util.PriorityQueue; public class Code05_SortArrayDistanceLessK { public static void sortedArrDistanceLessK(int[] arr, int k) { if (k == 0) { return; } // 默认小根堆 PriorityQueue heap = new PriorityQueue<>(); int index = 0; // 0...K-1 for (; index <= Math.min(arr.length - 1, k - 1); index++) { heap.add(arr[index]); } int i = 0; for (; index < arr.length; i++, index++) { heap.add(arr[index]); arr[i] = heap.poll(); } while (!heap.isEmpty()) { arr[i++] = 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); sortedArrDistanceLessK(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!"); } } ``` > 时间复杂度O(NlogK)

1.1.6.2 系统堆和手写堆选择

> > 使用系统提供的堆：如果我们只是要依次拿最大值，那么做成大根堆，如果我们要最小值我们把堆结构做成小根堆。就是简单的我们添加值，拿值，我们就选择系统提供的堆 > 选择手写堆：如果已经放到系统堆中的元素，加入我们根据需求会在放入堆之后要改动这些元素的值，系统堆并不保证弹出来的东西是正确的，这个时候需要我们手动写一个我们自定义的堆。虽然存在那种排好堆改某些元素让其重新有序的堆结构，但是实质上它是重新扫每个元素去heapinsert，代价太高。手动改写堆的例子例如Dijkstra算法就存在改写堆的优化 ```Java package class04; import java.util.ArrayList; import java.util.Comparator; import java.util.HashMap; import java.util.PriorityQueue; public class Code03_Heap02 { // 堆 public static class MyHeap { // 堆结构，数组实现 private ArrayList heap; // 任意一个元素，我们记录它在我们堆上的位置信息（反向表），此时我们找到我们要改的元素的位置就O(1) private HashMap indexMap; // 堆大小 private int heapSize; // 比较规则 private Comparator super T> comparator; // 构造 public MyHeap(Comparator super T> com) { heap = new ArrayList<>(); indexMap = new HashMap<>(); heapSize = 0; comparator = com; } 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); // 由于依次添加元素，添加进来的元素位置就是heapSize indexMap.put(value, heapSize); heapInsert(heapSize++); } // 弹出0号位置的元素，要同步堆和字典的操作 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还是heapify,但是两个操作只会命中一个 heapInsert(valueIndex); heapify(valueIndex, heapSize); } // heapInsert时，需要用我们自己的比较器进行比较 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 largest = left + 1 < heapSize && (comparator.compare(heap.get(left + 1), heap.get(left)) < 0) ? left + 1 : left; largest = comparator.compare(heap.get(largest), heap.get(index)) < 0 ? largest : index; if (largest == index) { break; } swap(largest, index); index = largest; left = index * 2 + 1; } } // 每次交换，不经要交换堆中两个位置的元素，在我们的字典中也要要换位置 private void swap(int i, int j) { T o1 = heap.get(i); T o2 = heap.get(j); heap.set(i, o2); heap.set(j, o1); indexMap.put(o1, j); indexMap.put(o2, 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 { @Override public int compare(Student o1, Student o2) { return o1.age - o2.age; } } public static void main(String[] args) { Student s1 = null; Student s2 = null; Student s3 = null; Student s4 = null; Student s5 = null; Student s6 = null; s1 = new Student(2, 50, 11111); s2 = new Student(1, 60, 22222); s3 = new Student(6, 10, 33333); s4 = new Student(3, 20, 44444); s5 = new Student(7, 72, 55555); s6 = new Student(1, 14, 66666); PriorityQueue heap = new PriorityQueue<>(new StudentComparator()); heap.add(s1); heap.add(s2); heap.add(s3); heap.add(s4); heap.add(s5); heap.add(s6); while (!heap.isEmpty()) { Student cur = heap.poll(); System.out.println(cur.classNo + "," + cur.age + "," + cur.id); } System.out.println("==============="); MyHeap myHeap = new MyHeap<>(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); } System.out.println("==============="); s1 = new Student(2, 50, 11111); s2 = new Student(1, 60, 22222); s3 = new Student(6, 10, 33333); s4 = new Student(3, 20, 44444); s5 = new Student(7, 72, 55555); s6 = new Student(1, 14, 66666); heap = new PriorityQueue<>(new StudentComparator()); heap.add(s1); heap.add(s2); heap.add(s3); heap.add(s4); heap.add(s5); heap.add(s6); s2.age = 6; s4.age = 12; s5.age = 10; s6.age = 84; while (!heap.isEmpty()) { Student cur = heap.poll(); System.out.println(cur.classNo + "," + cur.age + "," + cur.id); } System.out.println("==============="); s1 = new Student(2, 50, 11111); s2 = new Student(1, 60, 22222); s3 = new Student(6, 10, 33333); s4 = new Student(3, 20, 44444); s5 = new Student(7, 72, 55555); s6 = new Student(1, 14, 66666); myHeap = new MyHeap<>(new StudentComparator()); myHeap.push(s1); myHeap.push(s2); myHeap.push(s3); myHeap.push(s4); myHeap.push(s5); myHeap.push(s6); s2.age = 6; myHeap.resign(s2); s4.age = 12; myHeap.resign(s4); s5.age = 10; myHeap.resign(s5); s6.age = 84; myHeap.resign(s6); while (!myHeap.isEmpty()) { Student cur = myHeap.pop(); System.out.println(cur.classNo + "," + cur.age + "," + cur.id); } // 对数器 System.out.println("test begin"); int maxValue = 100000; int pushTime = 1000000; int resignTime = 100; MyHeap test = new MyHeap<>(new StudentComparator()); ArrayList list = new ArrayList<>(); for(int i = 0 ; i < pushTime; i++) { Student cur = new Student(1,(int) (Math.random() * maxValue), 1000); list.add(cur); test.push(cur); } for(int i = 0 ; i < resignTime; i++) { int index = (int)(Math.random() * pushTime); list.get(index).age = (int) (Math.random() * maxValue); test.resign(list.get(index)); } int preAge = Integer.MIN_VALUE; while(test.isEmpty()) { Student cur = test.pop(); if(cur.age < preAge) { System.out.println("Oops!"); } preAge = cur.age; } System.out.println("test finish"); } } ```

1.2 比较器

> 1、比较器的实质就是重载比较运算符 2、比较器可以很好的应用在特殊标准的排序上 3、比较器可以很好的应用在根据特殊标准排序的结构上 > 任何有序结构，我们可以传入我们的比较器，自定义我们自己的排序规则，不传它会按自己默认的规则排序 4、写代码变得异常容易，还用于泛型编程 > 比较规则中o1,o2，比较器返回负数表示o1要排在前面，返回正数表示o1要排在后面，返回0表示o1和o1相等无需排序。在java中自定义的比较器（MyComparator）实现Comparator接口，实现该接口中的compare方法，自定义我们的比较规则。 > 使用示例：Arrays.sort(student, new MyComparator()) ```Java package class04; import java.util.Arrays; import java.util.Comparator; import java.util.PriorityQueue; import java.util.TreeSet; public class Code01_Comparator { // 自定义我们的排序对象 public static 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; } } public static class IdAscendingComparator implements Comparator { // 返回负数的时候，第一个参数排在前面 // 返回正数的时候，第二个参数排在前面 // 返回0的时候，谁在前面无所谓 @Override public int compare(Student o1, Student o2) { return o1.id - o2.id; } } public static class IdDescendingComparator implements Comparator { @Override public int compare(Student o1, Student o2) { return o2.id - o1.id; } } public static class AgeAscendingComparator implements Comparator { @Override public int compare(Student o1, Student o2) { return o1.age - o2.age; } } public static class AgeDescendingComparator implements Comparator { @Override public int compare(Student o1, Student o2) { return o2.age - o1.age; } } public static class AgeShengIdSheng implements Comparator { @Override public int compare(Student o1, Student o2) { return o1.age != o2.age ? (o1.age - o2.age) : (o1.id - o2.id); } } // 先按照id排序，id小的，放前面； // id一样，age大的，前面； public static class IdInAgeDe implements Comparator { @Override public int compare(Student o1, Student o2) { return o1.id != o2.id ? o1.id - o2.id : ( o2.age - o1.age ); } } public static void printStudents(Student[] students) { for (Student student : students) { System.out.println("Name : " + student.name + ", Id : " + student.id + ", Age : " + student.age); } } public static void printArray(Integer[] arr) { if (arr == null) { return; } for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } System.out.println(); } public static class MyComp implements Comparator { @Override public int compare(Integer o1, Integer o2) { return o2 - o1; } } public static class AComp implements Comparator{ // 如果返回负数，认为第一个参数应该拍在前面 // 如果返回正数，认为第二个参数应该拍在前面 // 如果返回0，认为谁放前面都行 @Override public int compare(Integer arg0, Integer arg1) { return arg1 - arg0; // return 0; } } public static void main(String[] args) { Integer[] arr = {5,4,3,2,7,9,1,0}; Arrays.sort(arr, new AComp()); for(int i = 0 ;i < arr.length;i++) { System.out.println(arr[i]); } System.out.println("==========================="); Student student1 = new Student("A", 2, 20); Student student2 = new Student("B", 3, 21); Student student3 = new Student("C", 1, 22); Student[] students = new Student[] { student1, student2, student3 }; System.out.println("第一条打印"); Arrays.sort(students, new IdAscendingComparator()); printStudents(students); System.out.println("==========================="); Arrays.sort(students, new IdDescendingComparator()); printStudents(students); System.out.println("==========================="); Arrays.sort(students, new AgeAscendingComparator()); printStudents(students); System.out.println("==========================="); //// //// Arrays.sort(students, new AgeDescendingComparator()); //// printStudents(students); //// System.out.println("==========================="); // // Arrays.sort(students, new AgeShengIdSheng()); // printStudents(students); // // System.out.println("==========================="); // System.out.println("==========================="); // System.out.println("==========================="); // // PriorityQueue maxHeapBasedAge = new PriorityQueue<>(new AgeDescendingComparator()); // maxHeapBasedAge.add(student1); // maxHeapBasedAge.add(student2); // maxHeapBasedAge.add(student3); // while (!maxHeapBasedAge.isEmpty()) { // Student student = maxHeapBasedAge.poll(); // System.out.println("Name : " + student.name + ", Id : " + student.id + ", Age : " + student.age); // } // System.out.println("==========================="); PriorityQueue minHeapBasedId = new PriorityQueue<>(new AgeAscendingComparator()); minHeapBasedId.add(student1); minHeapBasedId.add(student2); minHeapBasedId.add(student3); while (!minHeapBasedId.isEmpty()) { Student student = minHeapBasedId.poll(); System.out.println("Name : " + student.name + ", Id : " + student.id + ", Age : " + student.age); } System.out.println("==========================="); System.out.println("==========================="); System.out.println("==========================="); TreeSet treeAgeDescending = new TreeSet<>(new AgeAscendingComparator()); treeAgeDescending.add(student1); treeAgeDescending.add(student2); treeAgeDescending.add(student3); Student studentFirst = treeAgeDescending.first(); System.out.println("Name : " + studentFirst.name + ", Id : " + studentFirst.id + ", Age : " + studentFirst.age); Student studentLast = treeAgeDescending.last(); System.out.println("Name : " + studentLast.name + ", Id : " + studentLast.id + ", Age : " + studentLast.age); System.out.println("==========================="); } } ```