1. 堆
堆结构就是用数组实现的完全二叉树结构，对于结点i，左孩子2*i+1、右孩子2*i+2、父节点（i-1）/ 2。
- 完全二叉树中如果每棵子树的最大值都在顶部就是大根堆
- 完全二叉树中如果每棵子树的最小值都在顶部就是小根堆
- 堆结构的heapInsert与heapify操作
- 堆结构的增大和减少
- 优先级队列结构，就是堆结构
1.1 堆的构建（大顶堆）
方法:
先给出一个序列：[4,6,5,8,9]
图解流程:
这个过程我们也叫做堆结构的heapInsert(一个新结点加入到堆中依次向上比对的过程)看具体的代码：
for(int i = 0; i < arr.length; i++) {
heapInsert(arr, i);
}
public static void heapInsert(int[] arr, int index) {
//当前子节点和父节点值比较，满足条件进行交换
while(arr[index] > arr[(index - 1) / 2]) {
//这里swap就是一个交换函数
swap(arr, index, (index - 1) / 2);
index = (index - 1) / 2;
}
}
堆结构的heapify的过程：
当我们形成一个大顶堆时，当堆中一个数据突然发生变化（变小）时，会有可能使得大顶堆不存在，得做下沉操作，heapify的过程就是使得该完全二叉树重新变成大顶堆。
就是将当前的结点与其左右子节点进行比较，大的进行交换
public static void heapify(int[] arr, int index, int size) {
//左子节点
int left = index * 2 + 1;
while (left < size) {
//两个孩子中，谁的值大，把下标给largest
int largest = left + 1 < size && 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;
}
}
1.2 堆排序
第一步：这就是堆排序的主要代码，先将无序的序列通过heapInsert的过程变成大顶堆；
第二步：把最后一个数与堆顶的数进行交换，size-1；
第三步：通过heapify的过程重新构建大根堆；
接下来的过程就是最后一个数与堆顶的数进行比较，size-1,再次重新构成大根堆，以此类推最终数组的顺序就是从小 到大的一个排序。
所有代码如下:
public class HeapSortV2 {
public static void main(String[] args) {
int[] arr = {10,9,40,30,28,-5,29};
System.out.println("排序前：" + Arrays.toString(arr));
heapSort(arr);
System.out.println("排序后:" + Arrays.toString(arr));
}
public static void heapSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
//给定一个数组，我们先要实现的就是根据数组形成大根堆，我们用heapInsert
for (int i = 0; i < arr.length; i++) {
heapInsert(arr, i);
}
//我们是如何根据大根堆来完成排序的呢，我们分析大根堆的根节点是当前数组中的最大的值
//我们将根节点的数字与叶子节点的最后一个值进行交换，并将size-1
int size = arr.length;
swap(arr, 0, --size);
while (size > 0) {
heapify(arr, 0, size);
swap(arr, 0, --size);
}
}
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;
}
}
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void heapify(int[] arr, int index, int size) {
//左子节点
int left = index * 2 + 1;
while (left < size) {
//两个孩子中，谁的值大，把下标给largest
int largest = left + 1 < size && 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;
}
}
}
运行结果:
1.3 题目练习
题目描述：
已知一个几乎有序的数组，几乎有序是指，如果把数组排好顺序的话，每个元素移动的距离可以不超过k，并且k相对于数组来说比较小。请选择一个合适的排序算法针对这个数据进行排序。题解
由于数组是几乎有序的，假如在第k+1个数之后存在最小值，那么元素移动到第一个位置需要移动超过k次，不符合，所以最小值必在前k+1个数里。
可以选择k+1大小的小根堆进行排序，先扫描数组的前k+1个数构建小根堆。然后取出堆顶元素放在数组的第1个位置，并把数组的第k+2个数插入小根堆。再取出堆顶元素放在数组的第2个位置，并把数组的第k+3个数插入小根堆……依次类推，扫描完数组后，把小根堆依次出堆即可。
代码:
public class SortArrayDistanceLessK {
public void sortedArrDistanceLessK(int[] arr, int k) {
//优先队列默认小根堆
PriorityQueue<Integer> heap = new PriorityQueue<>();
int index = 0;
for (int i = 0; i < arr.length; i++) {
heap.add(arr[i]); // 入堆
if (i > k) { //当扫描到完前k+1个数后，堆顶元素出堆，并放入数组的对应位置
arr[index++] = heap.poll();
}
}
//扫描完数组，依次出堆即可把剩余元素排完
while (!heap.isEmpty()) {
arr[index++] = heap.poll();
}
}
}
2. 比较器
比较器的使用
1）比较器的实质就是重载比较运算符
2）比较器可以很好的应用在特殊标准的排序上
3）比较器可以很好的应用在根据特殊标准排序的结构上
代码:
import java.util.Arrays;
import java.util.Comparator;
public class Code03_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;
}
@Override
public String toString() {
return "Student{" +
"name='" + name + '\'' +
", id=" + id +
", age=" + age +
'}';
}
}
public static class IdAAscendingComparator implements Comparator<Student> {
// 返回负数的时候，第一个参数排在前面
// 返回正数的时候，第二个参数排在前面
// 返回0的时候， 谁在前面无所谓
@Override
public int compare(Student o1, Student o2) {
return o1.id - o2.id;
// return 0;
}
}
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 void main(String[] args) {
int[] arr = {5,4,3,2,7,9,1,0};
Arrays.sort(arr);
System.out.println(Arrays.toString(arr));
System.out.println("=======================");
Student studnet1 = new Student("A", 2, 20);
Student studnet2 = new Student("B", 3, 21);
Student studnet3 = new Student("C", 1, 22);
Student[] students = {studnet1, studnet2, studnet3};
System.out.println("第一条打印");
System.out.println("==========id升序排序==========");
Arrays.sort(students, new IdAAscendingComparator());
System.out.println(Arrays.toString(students));
System.out.println("==========id降序排序==========");
Arrays.sort(students, new IdDescendingComparator());
System.out.println(Arrays.toString(students));
System.out.println("==========Age升序排序==========");
Arrays.sort(students, new AgeAscendingComparator());
System.out.println(Arrays.toString(students));
System.out.println("==========Age降序排序==========");
Arrays.sort(students, new AgeDescendingComparator());
System.out.println(Arrays.toString(students));
}
}
运行结果:
import java.util.Comparator;
import java.util.PriorityQueue;
public class HeapTest {
public static void main(String[] args) {
PriorityQueue<Integer> heap = new PriorityQueue<>(new ACom());
heap.add(6);
heap.add(9);
heap.add(3);
heap.add(2);
heap.add(10);
while (!heap.isEmpty()) {
System.out.println(heap.poll());
}
}
public static class ACom implements Comparator<Integer> {
// 如果返回负数，认为第一个参数应该放在上面
// 如果返回正数，认为第二个参数放在上面
// 如果返回0， 认为谁放前面都行
@Override
public int compare(Integer o1, Integer o2) {
return o1 - o2;
}
}
}
运行结果: