大小堆
二叉树的性质：
大小堆虽然是用数组存储的数据结构，但是其思想用到了完全二叉树的性质，因此需要知道这些内容：
满二叉树的定义：
在一棵二叉树中，如果所有的分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。
完全二叉树的定义：
对一棵具有n个结点的二叉树按层序编号，如果编号为$i(1≤i≤n)$的结点与同样深度的满二叉树中编号为$i$的结点在二叉树中位置完全相同，则这棵二叉树称为完全二叉树。
性质1：
在二叉数的第$i$层至多有$2^{i-1}$个结点
性质2：
深度为k的二叉树至多有$2^{k}-1$个结点($k≥1$)
性质3：
对任何一棵二叉树T,如果其终端节点数为$n_0$,度为2的结点数为$n_2$,则$n_0=n_2+1$
推理过程：
- 假设$n_0$是度为$0$的结点数，假设$n_1$是度为$1$的结点数,假设$n_2$是度为$2$的结点数,则树T的总结点数：$n=n_0+n_1+n_2$
- $n_1$和$n_2$因为分别有一个节点和两个节点，因此总根数：$n_1+2*n_2$
- 除了根节点以外，每个节点都有一个对应的分支，因此总根数：$n-1$
- 可以推的：$n-1 = n_1 + 2 * n_2 => n_0+n_1+n_2-1=n_1 + 2 * n_2 => n_0 = n_2 + 1$
性质4：
具有n个结点的完全二叉树的深度为$\lfloor{log_2^n}\rfloor + 1(\lfloor{x}\rfloor 表示不大于x的最大整数)$
推理：
- 深度为$k$的完全二叉树满足$2^{k-1}-1≤n≤2^{k}-1$,可以推的$2^{k-1}≤n＜2^k$，可以推的$k-1≤log_2^n＜k$,k作为整数，因此$k=\lfloor{log_2^n}\rfloor + 1(\lfloor{x}\rfloor 表示不大于x的最大整数)$
性质5:
如果对一棵有n个结点的完全二叉树(其深度为$\lfloor{log_2^n}\rfloor + 1(\lfloor{x}\rfloor 表示不大于x的最大整数)$)的结点按层序编号(从第1层到$\lfloor{log_2^n}\rfloor + 1$，每层从左到右)，对任一结点$i(1≤i≤n)$有：
- 如果$i=1$，则结点$i$是二叉树的根，无双亲;如果$i>1$，则其双亲是结点$\lfloor{i/2}\rfloor$
- 如果$2i＞n$，则结点$i$无左孩子(结点$i$为叶子结点);否则其左孩子是结点$2i$
- 如果$2i+1＞n$，则结点$i$无右孩子;否则其右孩子是结点$2i+1$
大小堆的定义：
堆是具有下列性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆，或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。
如果有一个关键码的集合K = {k0，k1， k2，…，kn-1}，把它的所有元素按完全二叉树 的顺序存储方式存储在一个一维数组中，并满足：$k_i≤k_{2i+1}且k_i≤k_{2i+2}(k_i≥k_{2i+1}且k_1≥k_{2i+2}) i=0,1,2...$ 且 ，则称这个堆为最小堆(或最大堆)。
最大堆：
思路：
- 声明一个数组heap存储元素，声明两个变量limit和size，分别表示堆的容量和大小
- 根据堆和完全二叉树的定义，可以知道结点$i$的左右子节点必然在数组$2i+1$和$2i+2$上
- 声明一个方法push，表示插入元素，首先将元素插入到末尾，然后执行heapInsert方法，size++
- heapInsert方法参考的堆的结点$i$的左右子节点必然在数组$2i+1$和$2i+2$上，
- 那么当前结点$j$如果是左结点，则父节点$(j-1)/2$，
- 如果当前结点$j$是右结点，则直接$(j-1)/2 = (2*i +2 - 1)/2 =i-1/2$,int类型整数除2，直接向下取整，因此等于$i$,
- 所以左右结点$j$的父节点必然是$(j-1) / 2$
- heapInsert方法的参数是数组$arr$和$index$，$arr$表示当前堆数组，$index$表示当前插入数组的位置
- 拿$index$和它的父节点$(index-1)/2$的元素比较,$arr[index] > arr[(index-1)/2]$，则将$arr[index]$和$arr[(index-1)/2]$上的元素交换，然后$index = (index-1)/2$,继续上一次的比较，直到比父亲元素小，或者到$0$位置
- heapInsert方法参考的堆的结点$i$的左右子节点必然在数组$2i+1$和$2i+2$上，
private void swap(int[] arr,int i,int j){
int tmp = arr[i];
int arr[i] = arr[j];
int arr[j] = tmp;
}
private void heapInsert(int[] arr,int index){
while(arr[index] > arr[(index-1)/2]){
swap(arr,index,(index-1)/2);
index = (index-1)/2;
}
}
public void push(int value){
if(this.heapSize == this.limit){
throw new RunTimeException("heap is full");
}
heap[heapSize] == value;
heapInsert(arr,heapSize++);
}
-
声明一个方法pop,表示弹出最大值，首先得到$ans = arr[0]$的值，然后拿$0$和$heapSize$的元素互换，然后heapSIze--,这样就能弹出最大栈的数值，然后再调用heapify方法，将栈顶的元素向下降，放到一个合理的位置
- heapify方法需要三个参数，分别是数组$arr[]$,$index$,$heapSize$,
- 得到当前index的左节点的下标:$left：2index+1$，右节点的下标:$right:2index+2 = left + 1$
- 判断左右节点谁大，谁大，赋值给largest，然后largest和index判断谁元素大
- index大，则退出当前循环
- largest大，则将index和largest的元素互换，index移到largest小标处，然后得到新的left和right，重复上面过程，直到left超出heapSize范围
private 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 int pop(){ int ans = heap[0]; swap(heap,0,--this.heapSize); heapify(arr,0,this.heapSize); return ans; }完整版本:
public class MyMaxHeap{ private int[] heap; private final int limit; private int heapSize; public MyMaxHeap(int limit){ heap = new int[limit]; this.limit = limit; this.heapSize = 0; } private void swap(int[] arr,int i,int j){ int tmp = arr[i]; int arr[i] = arr[j]; int arr[j] = tmp; } private void heapInsert(int[] arr,int index){ while(arr[index] > arr[(index - 1)/2]){ swap(arr,index,(index-1)/2); index = (index - 1)/2; } } public void push(int value){ if(this.heapSize == this.limit){ return new RuntimeException("heap is full"); } heap[heapSize]=value; heapInsert(heap,heapSize++); } private int heapify(int[] arr,int index,int heapSize){ int left = index * 2+1; while(left < heapSize){ int target = 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 int pop(){ if(heapSize == 0){ throw new RunTimeException("No element"); } int ans = this.heap[0]; swap(heap,0,--this.heapSize); heapify(heap,0,this.heapSize); return ans; } public boolean isEmpty(){ return this.heapSize == 0; } public boolean isFull(){ return this.heapSize == this.limit; } }
堆排序
定义：将待排序的数组构造成一个大顶堆。此时，整个数组的最大值就是堆顶的根结点。将根节点和末尾元素互换，然后将$n-1$个元素重新构造成一个堆，这样就会得到$n$个元素中的次大值。反复执行，便能得到一个有序数组了。
public void heapSort(int[] arr){
if(arr == null || arr.length < 2){
return;
}
/*
for(int i = 0;i < arr.length;i++){
heapInsert(arr,i);
}
*/
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){
heapify(arr,0,heapSize);
swap(arr,0,--heapSize);
}
}
private 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;
}
}
private void heapInsert(int[] arr,int index){
while(arr[index] > arr[(index-1)/2]){
swap(arr,index,(index-1)/2);
index = (index-1)/2;
}
}
private void swap(int[] arr,int i,int j){
int tmp = arr[i];
int arr[i] = arr[j];
int arr[j] = tmp;
}
排序元素移动小于k的数组
问题：已知一个几乎有序的数组(几乎有序是指如果把数组排好序的话，每个元素移动的距离不超过k，且k相较于数组而言较小).请选择一个合适的排序算法对这个数据进行排序
思路：
- 声明一个优先级队列(默认小根堆)，存储数组的前k个元素，前k个元素的最小值就可以得到。
- 然后弹出第一个元素，得到k个元素中的最小值，放到数组i（初始0）中，然后i++,然后队列放入数组k+1个元素，然后弹出。
- 上述过程，反复执行，最后把队列中剩余元素放入数组中，即是一个有序的数组。
public void sortedArrDistanceLessK(int[] arr,int k){
if(k == 0){
return;
}
PriorityQueue<Integer> queue = new PriorityQueue<>();
int index = 0
for(;index <= Math.min(arr.length-1,k-1);index++){
queue.add(arr[index]);
}
int i = 0;
for(; index < arr.length;i++,index++){
queue.add(arr[index]);
arr[i] = queue.poll();
}
while(!queue.isEmpty()){
arr[i++] = queue.poll();
}
}