一、堆和相关操作

1. 堆结构就是用数组实现的完全二叉树结构
   size指有多少个节点
   i位置，左孩子2i+1，右孩子2i+2，父节点(i-1)/2向下取整
2. 完全二叉树中如果每棵子树的最大值都在顶部就是大根堆
3. 完全二叉树中如果每棵子树的最小值都在顶部就是小根堆
4. 堆结构的heapInsert与heapify操作

• （１）插入操作heapInsert
  插入尾部，不断与父节点比较　　O(logN)

//某个数现在处在index位置，往上继续移动
public static void heapInsert(int[] arr,int index){while(arr[index] > arr[(index - 1) / 2]){  //index位置的数>其父节点　或者　已经到头部swap(arr,index,(index - 1) / 2);  //交换index = (index - 1) / 2;  //index的值变换到原父节点处}
}

• （2）大根堆取最大值操作
  1、先返回大根堆的最大值（即根）heapsize–
  2、将最后一个节点放到根处，一次与左右孩子比较，不断下沉，直到左右孩子都比它小，或者没有孩子为止

• （3）能否往下移动heapify
  O(logN)

//某个数在index位置，能否往下移动
public static void heapify(int[] arr,int index,int heapSize){int left = index * 2 + 1; //左孩子下标while(left < heapSize){ //当下方还有孩子的时候，左孩子<size，则一定有右孩子<size//两个孩子中，谁的值大，把下标给largestint largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;//父亲和较大孩子之间，谁的值大，把下标给largestlargest = arr[largest] > arr[index] ? largest : index;if(largest == index){   //如果和孩子相比，最大的值就是index，则跳出break;}swap(arr,largest,index);  //否则，交换index和largest的值index = largest;          //index下移到最大值处的位置left = index * 2 + 1;     //更新left，继续循环}
}

• （4）改变第i个节点的值
  大根堆：
  1、如果i位置的值变小了 => i位置往下进行heapify运算
  2、如果i位置的值变大了 => i位置往上进行heapInsert运算

5. 堆结构的增大和减小
6. 优先级队列结构，就是堆结构
   （堆排序往往没有堆结构重要）

PriorityQueue<Integer>heap = new PriorityQueue<>(); //小根堆

二、堆排序 *

• 时间复杂度：O(NlogN)
• 空间负责都：O(1)
• 大根堆：
  1、将数列中的数依次逐个加入，并排成大根堆。
  2、将第一个元素位置的数（即最大值）与最后一个位置的数交换，并返回最大值
  3、重复以上过程，不断返回后就得到了降序序列

package com.godzuo.java;
import java.util.Arrays;public class HeapSort {public static void heapSort(int[] arr){if(arr == null || arr.length < 2) return;
//        for(int i = 0;i < arr.length;i++){  //O(N)
//            heapInsert(arr,i);  //建成大根堆  O(logN)
//        }for(int i = arr.length - 1;i >= 0;i--){  //O(N),时间复杂度没有变，但是速度变快了，因为后面排序为O(NlogN)。    如果只是变成堆，则应该选择这种方法。heapify(arr,i,arr.length);  }int heapSize = arr.length;swap(arr, 0, --heapsize);  //0位置的数与堆上最后一个位置的数交换，交换之后堆的大小--while (heapsize > 0) {  //O(N)heapify(arr, 0, heapsize); //0位置上的数往下，重新调整为大根堆  O(logN)swap(arr, 0, --heapsize);  //继续交换，--　  O(1)}       }
}//建立大根堆public static void heapInsert(int[] arr,int i){while (arr[i]>arr[(i-1)/2]){swap(arr,i,(i-1)/2);i = (i-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 heapSize){int left = index*2+1;while (left < heapSize){int largest = left+1 < heapSize && arr[left+1] > arr[left] ? left+1 : left;largest = arr[largest] > arr[index] ? largest : index;if (largest == index){break;}swap(arr,largest,index);index = largest;left = index*2+1;}}public static void main(String[] args) {int[] arr = {1,3,2,6,5,9};heapSort(arr);System.out.println(Arrays.toString(arr));}
}

• 改进：
  不是逐个加入后调整，而是全部加入后，从后从右往左往上做heapify。
  

三、堆排序题目拓展

【题目】
已知一个几乎有序的数组，几乎有序是指，如果把数组排好顺序的话，每个元素移动的距离可以不超过k，并且k相对于数组来说比较小。请选择一个合适的排序算法针对这个数据进行排序。
【分析】
时间复杂度：O(Nlogk)近似可等于O(N)

public class SortArrayDistanceLessK(int[] arr,int k){//默认小根堆PriorityQueue<Integer> heap = new PriorityQueue<>();int index = 0;for(;index <= Math.min(arr.length,k);index++){heap.add(arr[index]);   // 前k个数排成小根堆}int i = 0;for(;index < arr.length;i++,index++){heap.add(arr[index]); //加一个值arr[i] = heap.poll(); //弹一个值}while(!heap.isEmpty()){arr[i++] = heap.poll;  //弹出剩下的}
}

四、堆结构

//Java默认小根堆
PriorityQueue<Integer> heap = new PriorityQueue<>(); heap.add(8);
heap.add(4);
heap.add(9);
heap.add(10);
heap.add(3);while(!heap.isEmpty())System.out.println(heap.poll());

1. 扩容
   扩容次数：logN
   每次扩容代价：O(N)
   扩容的总代价：O(NlogN)
   平均扩容代价：O(NlogN)/N=O(logN)

2. 系统自带的堆结构
   1、add加入、poll弹出
   方便，但是不支持已经形成的堆，人为改值等操作后，用很小的代价重新调整为堆
   2、自己手写的堆可以高效实现

五、比较器

C++重载比较运算符 == Java的比较器

package com.godzuo.java;import java.util.Arrays;
import java.util.Comparator;public class 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> {//按照Id升序排列//！！！下面！！！//返回负数的时候，第一个参数排在前面//返回正数的时候，第二个参数排在前面//返回0的时候，谁在前面无所谓@Overridepublic int compare(Student o1, Student o2) {return o1.id - o2.id;//if(o1.id < o2.id)//	return -1;//if(o1.id > o2.id)//	return 1;//return 0;}}public static class IdDescendingComparator implements Comparator<Student> {//ID降序@Overridepublic int compare(Student o1, Student o2) {return o2.id - o1.id;}}public static class AgeAscendingComparator implements Comparator<Student> {//年龄升序@Overridepublic int compare(Student o1, Student o2) {return o1.age - o2.age;}}public static class AgeDescendingComparator implements Comparator<Student> {//年龄降序的比较器@Overridepublic int compare(Student o1, Student o2) {return 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);}System.out.println("===========================");}public static void main(String[] args) {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[] { student3, student2, student1 };printStudents(students);Arrays.sort(students, new IdAscendingComparator()); //系统比较大小：数组、策略printStudents(students);Arrays.sort(students, new IdDescendingComparator());printStudents(students);Arrays.sort(students, new AgeAscendingComparator());printStudents(students);Arrays.sort(students, new AgeDescendingComparator());printStudents(students);//自带的堆结构PriorityQueue<Student> heap = new PriorityQueue<>(new AgeAscendingComparator());heap.add(student1);heap.add(student2);heap.add(student3);while (!heap.isEmpty()){Student student = heap.poll();System.out.println("Name : " + student.name + ", Id : " + student.id + ", Age : " + student.age);}}
}

• 比较器还能用在有序的结构里
  1、不传东西，默认以小根堆组织

public static void main(String[] args){PriorityQueue<Integer> heap = new PriorityQueue<>(); heap.add(8);heap.add(4);heap.add(9);heap.add(10);heap.add(3);while(!heap.isEmpty())System.out.println(heap.poll());
}

2、传比较器，以大根堆排序

public class HeapTest{public static class AComp implements Comparator<Integer> {//！！！下面！！！//返回负数，第一个参数排在上面//返回正数，第二个参数排在上面//返回0的时候，谁在前上无所谓@Overridepublic int compare(Integer arg0, Integer arg1) {return arg1 - arg2;}}public static void main(String[] args){PriorityQueue<Integer> heap = new PriorityQueue<>(new AComp()); //传入比较器heap.add(8);heap.add(4);heap.add(9);heap.add(10);heap.add(3);while(!heap.isEmpty())System.out.println(heap.poll());}
}

• 比较器的实质就是重载比较运算符
• 比较器可以很好的应用在特殊标准的排序上
• 比较器可以很好的应用在根据特殊标准排序的结构上（如堆）

六、基数排序

不基于比较的排序都是根据数据状况做的排序，没有基于比较的排序那么广的应用范围。（eg：计数排序、基数排序）

依次按照个、十、百、千、万等，排序放入桶中，再按顺序倒出来。
优先级最高的，最后排序。

基数排序：要有进制（进制位数 == 桶的个数）

import java.util.Arrays;public class RadixSort{//only for no-negative valuepublic static void radixSort(int[] arr){if(arr == null || arr.length < 2){return;}radixSort(arr,0,arr.length - 1,maxbits(arr));}public static int maxbits(int[] arr){int max = Integer.MIN_VALUE;for(int i = 0;i < arr.length;i++){max = Math.max(max,arr[i]);   //找到最大值}int res = 0;while(max != 0){res++;max /= 10;}return res;   //最大值有几(个十进制)位}//arr[begin...end]排序public static void radixSort(int[] arr,int L,int R,int digit){//arr数组，范围L到R，digit表示这一批数字中有多少(个十进制)位final int radix = 10;   //以10位基底int i = 0,j = 0;//有多少个数准备多少个辅助空间int[] bucket = new int[R - L + 1];for(int d = 1;d <= digit;d++){  //有多少位就进出桶多少次，即位数的遍历//10个空间//count  词频数组 => 前缀和//count[0]是当前位(d位)是0的数字有多少个//count[1]是当前位(d位)是(0和1)的数字有多少个//count[2]是当前位(d位)是(0、1和2)的数字有多少个//count[0]是当前位(d位)是(0~i)的数字有多少个int[] count = new int[radix];    //count[0...9]for(i = L;i <= R;i++){j = getDigit(arr[i],d); //d=1取出个位数字，d=2取出百位数字count[j]++;  //计算各个位置每种数的个数}for (i = 1;i < radix;i++){count[i] = count[i] + count[i - 1];  //计算前缀和}for(i = R;i >= L;i--){    //数组从右往左遍历j = getDigit(arr[i],d);  //将d位的数拿出来bucket[count[j] - 1] = arr[i];  //放到辅助数组所在片的最后一位count[j]--;  //j的前缀和-1}                                   //所有数出桶，放到bucket中for(i = L,j = 0;i <= R;i++,j++){arr[i] = bucket[j];             //把bucket中的数字导到arr里面}                                   }         //循环，下个位置的数字再出桶、入桶}public static int getDigit(int x,int d){return ((x / ((int) Math.pow(10,d - 1))) % 10);}
}

所有数从右往左遍历，放入所在片的最后一个位置，可以保证先入桶的先出桶；并且从右边出可以统计小于该数的数量，来确定自己的位置。