（一）堆
1，堆结构就是用数组实现的完全二叉树结构
2，完全二叉树中如果每棵子树的最大值都在顶部就是大根堆
3，完全二叉树中如果每棵子树的最小值都在顶部就是小根堆
4，堆结构的heapInsert与heapify操作
5，堆结构的增大和减少
6，优先级队列结构，就是堆结构
1.完全二叉树
原文链接：https://blog.csdn.net/Real_Fool_/article/details/113930623
高度为h、有n个结点的二叉树，当且仅当其每个结点都与高度为h的满二叉树中编号为1~n的结点一一对应时，称为完全二叉树，如图所示。其特点如下:
（1）若 i≤n/2，则结点i为分支结点，否则为叶子结点。
（2）叶子结点只可能在层次最大的两层上出现。对于最大层次中的叶子结点，都依次排列在该层最左边的位置上。
（3）若有度为1的结点，则只可能有一个，且该结点只有左孩子而无右孩子（重要特征）。
（4）按层序编号后，一旦出现某结点（编号为i）为叶子结点或只有左孩子，则编号大于i的结点均为叶子结点。
（5）若n为奇数，则每个分支结点都有左孩子和右孩子；若n为偶数，则编号最大的分支结点（编号为n/2）只有左孩子，没有右孩子，其余分支结点左、右孩子都有。
完全二叉树可以看成一个数组(从0起始出发)，设数组长度为n,在满足数组长度前提下，对于节点i:
- 左孩子：2*i+1
- 右孩子：2*i+2
- 父节点：(i-1)/2
完全二叉树的高度：节点个数是N,完全二叉树高度为( [logN]+1,[]表示向下取整)。
2.大根堆和小根堆
2.1 大根堆
大根堆（Max Heap）满足：
每个父结点的值，都大于等于它的子结点。
因此，整个堆的最大值一定在根结点。
2.2 小根堆
小根堆（Min Heap）正好相反：
每个父结点的值，都小于等于它的子结点。
因此，整个堆的最小值一定在根结点。
2.3 完全二叉树构成大根堆和小根堆
1.完全二叉树构成大根堆
代码：
package class003;
import java.util.Arrays;
public class Code_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--){
// heapify(arr,i,arr.length);
// }
int heapSize=arr.length;
swap(arr,0,--heapSize);
while(heapSize>0){//O(N)
heapify(arr,0,heapSize);//O(logN)
swap(arr,0,--heapSize);//O(1)
}
}
//某个数现在处在index的位置，往上继续移动
public static void heapInsert(int[] arr,int index){
//当前位置的数大于父位置的数，index和父位置做交换
//index变为父位置，继续判断是否交换，直到变为0位置
while(arr[index]>arr[(index-1)/2]){
swap(arr,index,(index-1)/2);
index=(index-1)/2;
}
}
//某个数在index位置，能否往下移动
public static void heapify(int[] arr,int index,int heapSize){
int left=index*2+1;//左孩子的下标
while(left<heapSize){//下方还有孩子时(左孩子)
//两个孩子中，谁的值大，把下标给largest
//右孩子存在，并且右孩子下标的值大于左孩子时，largest变量的下标变成右孩子下标，否则左孩子给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;
}
// public static void comparator(int[] arr){
// Arrays.sort(arr);
// }
public static void main(String[] args){
int []arr1={4,8,9,43,21};
int []arr2={11,43,32,12,24};
System.out.println("arr1："+ Arrays.toString(arr1));
heapSort(arr1);
System.out.println("arr1 heapSort: "+Arrays.toString(arr1));
System.out.println("arr2："+ Arrays.toString(arr2));
heapSort(arr2);
System.out.println("arr2 heapSort: "+Arrays.toString(arr2));
}
}
运行结果：
arr1：[4, 8, 9, 43, 21]
arr1 heapSort: [4, 8, 9, 21, 43]
arr2：[11, 43, 32, 12, 24]
arr2 heapSort: [11, 12, 24, 32, 43]
（1）建堆流程图：
原数组
[4,8,9,43,21]
↓ i=0，加入4
[4,8,9,43,21]
↓ i=1，8向上移动
[8,4,9,43,21]
↓ i=2，9向上移动
[9,4,8,43,21]
↓ i=3，43连续向上移动
[43,9,8,4,21]
↓ i=4，21向上移动
[43,21,8,4,9]
↓
大根堆建立完成
（2）排序流程图：
建立完成的大根堆
[43,21,8,4,9]
↓
43和最后一个数交换
[9,21,8,4 | 43]
↓ heapify
[21,9,8,4 | 43]
↓
21和堆最后一个数交换
[4,9,8 | 21,43]
↓ heapify
[9,4,8 | 21,43]
↓
9和堆最后一个数交换
[8,4 | 9,21,43]
↓ heapify
[8,4 | 9,21,43]
↓
8和堆最后一个数交换
[4 | 8,9,21,43]
↓
[4,8,9,21,43]
排序完成
注意，代码确实先建立了大根堆，只是随后又执行了“堆排序”，不断把堆顶最大值交换到数组末尾，所以最终得到的是升序数组。
问题：
（1）将大根堆的顶点删除时，调整回大根堆。分析：将大根堆的最后一个节点复制到第一个节点并删除最后一个节点（heapsize--），接着带入heapInsert循环中）
（2）将大根堆中的任意一个节点i的值替换为a,如何调整堆，让这个堆依然是堆。分析：如果这个被修改节点i的值a比原来更小，经历一个heapify调整;如果这个被修改节点i的值a比原来更大，经历一个heapInsert调整。
（3）在大根堆中插入/修改/移除任意一个数进行调整的时间复杂度级别。分析：完全二叉树的高度：节点个数是N,完全二叉树高度为( [logN]+1,[]表示向下取整)，所以这个过程的时间复杂度是O(logN)级别的。
3.堆排序
3.1 堆排序细节
实质：不断删除已经有序的堆的根节点，接着将[heapsize]上的数复制到[1]位置，heapsize--,然后根据大根堆或小根堆的调整方法（heapInsert，heapify）进行调整，形成新的堆，接着继续删除有序堆的节点循环下去。
堆排序复杂度：时间复杂度：O(N*logN),空间复杂度O(1)
1，先让整个数组都变成大根堆结构，建立堆的过程：
1）从上到下的方法，时间复杂度为O(N*logN)
2）从下到上的方法，时间复杂度为O(N)
2，把堆的最大值和堆末尾的值交换，然后减少堆的大小之后，再去调整堆，一直周而复始，时间复杂度为O(N*logN)
3，堆的大小减小成0之后，排序完成
对于给定的满二叉树(已经提前排列好，不需要heapinsert插入。)，设它的总节点个数为N,最底层节点的个数规模为N/2(精确计算是[N/2]+1，[]表示向下取整)，每个节点调用heapify一次（向下移动的次数）；倒数第二层节点的个数规模为N/4，每个节点需要调用heapify两次；倒数第三层节点的个数规模为N/8，每个节点需要调用heapify三次.....累加起来
T(N)=N/2*1+N/4*2+N/8*3+N/16*4+......
2T(N)=N/2*2+N/2*2+N/4*3+N/8*4+......
T(N)=N+N/2+N/4+.....=2N
所以时间复杂度为O(N)
3.2 堆排序拓展题目
问题：已知一个几乎有序的数组，几乎有序是指，如果把数组排好顺序的话，每个元素移动的距离可以不超过k，并且k相对于数组来说比较小，请选择一个合适的排序算法针对这个数据进行排序，要求复杂度低。
分析：设k=6,先建立一个大小为7的小根堆，为了简便说明，假设数组前7个数是{0,1,2,3,4,5,6},将它们放到小根堆里面去，遍历一遍后，小根堆的最小值一定在根节点，则7以后的数字不可能在0位置上，我们把小根堆的最小值弹出，然后把7放到小根堆中原来0的位置上；再遍历一遍，小根堆的最小值一定是1，再次弹出，接着把把8放到小根堆中原来1的位置上，如此循环......最后，数组空了，将最终那个小根堆里面的数依次弹出，即可得到全部有序的数组。该算法的时间复杂度由元素移动距离k决定，为O(N*logk)
解释：
第一次：
[0 1 2 3 4 5 6] 7 8 9 ...
└──小根堆────┘
弹出最小值 → arr[0]
第二次：
0 [1 2 3 4 5 6 7] 8 9 ...
└──小根堆────┘
弹出最小值 → arr[1]
第三次：
0 1 [2 3 4 5 6 7 8] 9 ...
└──小根堆────┘
弹出最小值 → arr[2]
代码：
package class003;
import java.util.PriorityQueue;
public class Code_SortArrayDistanceLessK {
public void sortedArrDistanceLessK(int[] arr,int k){
//java中的优先级队列，默认是小根堆
PriorityQueue<Integer>heap=new PriorityQueue<>();
int index=0;
for(;index<=Math.min(arr.length,k);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();
}
}
public static void main(String [] args){
PriorityQueue<Integer>heap=new PriorityQueue<>();
heap.add(8);
heap.add(4);
heap.add(4);
heap.add(9);
heap.add(10);
heap.add(3);
while (!heap.isEmpty()){
System.out.println(heap.poll());
}
}
}
运行结果：
3
4
4
8
9
10
注意：
1.在java中，如果数组不够用了，会发生动态扩容，如果数组扩容到N，那么它在这个过程中的扩容次数是logN,O(N)是扩容的代价，O(logN)是扩容的次数的代价,O(N*logN)是总代价
2.对于系统给的堆结构，它是一个黑盒，不支持在它原有的堆的基础上修改一个数字让它重新变回堆结构，只能一次一次地遍历整个数组，代价较高。因此自己手写堆的代价较低。
4.比较器的使用
1）比较器的实质就是重载比较运算符
2）比较器可以很好的应用在特殊标准的排序上
3）比较器可以很好的应用在根据特殊标准排序的结构上
（二）桶排序
桶排序思想下的排序
1）计数排序
2）基数排序
基数排序详解见王道《数据结构》课程：BV1b7411N798
分析：
1）桶排序思想下的排序都是不基于比较的排序
2）时间复杂度为O(N)，额外空间负载度O(M)
3）应用范围有限，需要样本的数据状况满足桶的划分
代码：
package class003;
import java.util.Arrays;
public class Code_RadixSort {
//only for no-negative value
public 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]排序
//dight表示最大位数
public static void radixSort(int[] arr,int L,int R,int digit){
final int radix=10;
int i=0,j=0;
//有多少个数准备多少个辅助空间
int[]bucket=new int[R-L+1];
for(int d=1;d<=digit;d++){//有多少位就进出几次
//10个空间
//count[0]当前位（d位）是0的数字有多少个
//count[1]当前位（d位）是(0和1)的数字有多少个
//count[2]当前位（d位）是（0，1，和2）的数字有多少个
//count[i]当前位（d位）是（0-i）的数字有多少个
int[] count=new int[radix];//count[0..9]
for(i=L;i<=R;i++){
j=getDigit(arr[i],d);
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);
bucket[count[j]-1]=arr[i];
count[j]--;
}
for(i=L,j=0;i<=R;i++,j++){
arr[i]=bucket[j];
}
}
}
public static int getDigit(int x,int d){
return ((x/((int)Math.pow(10,d-1)))%10);
}
public static void main(String [] args){
int []arr1={4,8,9,43,21,39,31};
int []arr2={11,43,32,12,24,};
System.out.println("arr1："+ Arrays.toString(arr1));
radixSort(arr1);
System.out.println("arr1 radixSort: "+Arrays.toString(arr1));
System.out.println("arr2："+ Arrays.toString(arr2));
radixSort(arr2);
System.out.println("arr2 radixSort: "+Arrays.toString(arr2));
}
}
运行结果：
arr1：[4, 8, 9, 43, 21, 39, 31]
arr1 radixSort: [4, 8, 9, 21, 31, 39, 43]
arr2：[11, 43, 32, 12, 24]
arr2 radixSort: [11, 12, 24, 32, 43]
代码流程解释：
原数组
[4,8,9,43,21,39,31]
第一轮
↓ 统计个位出现次数
count = [0,2,0,1,1,0,0,0,1,2]
↓ 做前缀和
count = [0,2,2,3,4,4,4,4,5,7]
↓ 从右往左放入bucket
bucket = [21,31,43,4,8,9,39]
↓ 拷贝回原数组
[21,31,43,4,8,9,39]
上一轮结果
[21,31,43,4,8,9,39]
第二轮
↓ 统计十位出现次数
count = [3,0,1,2,1,0,0,0,0,0]
↓ 做前缀和
count = [3,3,4,6,7,7,7,7,7,7]
↓ 从右往左放入bucket
bucket = [4,8,9,21,31,39,43]
↓ 拷贝回原数组
[4,8,9,21,31,39,43]
转载自 CSDN-专业IT技术社区
原文链接：https://blog.csdn.net/C__learner_/article/details/164325568
