[TOC]
# 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<Integer> 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<Integer>{
@Override
public int compare(Integer o1, Integer o2) {
return o2 - o1;
}
}
public static void main(String[] args) {
System.out.println("hello");
// 大根堆
PriorityQueue<Integer> 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<Integer> 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<T> {
// 堆结构，数组实现
private ArrayList<T> heap;
// 任意一个元素，我们记录它在我们堆上的位置信息（反向表），此时我们找到我们要改的元素的位置就O(1)
private HashMap<T, Integer> 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<Student> {
@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<Student> 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<Student> 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<Student> test = new MyHeap<>(new StudentComparator());
ArrayList<Student> 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<Student> {
// 返回负数的时候，第一个参数排在前面
// 返回正数的时候，第二个参数排在前面
// 返回0的时候，谁在前面无所谓
@Override
public int compare(Student o1, Student o2) {
return o1.id - o2.id;
}
}
public static class IdDescendingComparator implements Comparator<Student> {
@Override
public int compare(Student o1, Student o2) {
return o2.id - o1.id;
}
}
public static class AgeAscendingComparator implements Comparator<Student> {
@Override
public int compare(Student o1, Student o2) {
return o1.age - o2.age;
}
}
public static class AgeDescendingComparator implements Comparator<Student> {
@Override
public int compare(Student o1, Student o2) {
return o2.age - o1.age;
}
}
public static class AgeShengIdSheng implements Comparator<Student> {
@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<Student> {
@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<Integer> {
@Override
public int compare(Integer o1, Integer o2) {
return o2 - o1;
}
}
public static class AComp implements Comparator<Integer>{
// 如果返回负数，认为第一个参数应该拍在前面
// 如果返回正数，认为第二个参数应该拍在前面
// 如果返回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<Student> 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<Student> 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<Student> 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("===========================");
}
}
```
- 第一节 复杂度、排序、二分、异或
- 第二节 链表、栈、队列、递归、哈希表、顺序表
- 第三节 归并排序、随机快排介绍
- 第四节 比较器与堆
- 第五节 前缀树、桶排序以及排序总结
- 第六节 链表相关面试题总结
- 第七节 二叉树基本算法
- 第八节 二叉树的递归思维建立
- 第九节 贪心算法深度剖析
- 第十节 并查集、图相关算法介绍
- 第十一节 暴力递归思维、动态规划思维建立
- 第十二节 用简单暴力递归思维推导动态规划思维
- 第十三节 单调栈和窗口及其更新结构
- 第十四节 类似斐波那契数列的递归
- 第十五节 认识KMP算法与bfprt算法
- 第十六节 认识Manacher(马拉车)算法
- 第十七节 认识Morris遍历
- 第十八节 线段树
- 第十九节 打表技巧和矩阵处理技巧
- 第二十节 组累加和问题整理
- 第二十一节 哈希函数有关的结构和岛问题
- 第二十二节 解决资源限制类题目
- 第二十三节 有序表原理及扩展
- 第二十四节 AC自动机和卡特兰数
- 第二十五节 算法面试专题-链表
- 第二十六节 算法面试专题-二叉树
- 第二十七节 算法面试专题-字符串