建设银行 北京招聘网站,网站设计 品牌设计,创建网站公司好,制作微信小程序商城一、堆结构1#xff09;堆结构就是用数组实现的完全二叉树结构2#xff09;完全二叉树中如果每棵子树的最大值都在顶部就是大根堆3#xff09;完全二叉树中如果每棵子树的最小值都在顶部就是小根堆4#xff09;堆结构的heapInsert与heapify操作5#xff09;堆结构的增大ad…一、堆结构1堆结构就是用数组实现的完全二叉树结构2完全二叉树中如果每棵子树的最大值都在顶部就是大根堆3完全二叉树中如果每棵子树的最小值都在顶部就是小根堆4堆结构的heapInsert与heapify操作5堆结构的增大add和减少poll6优先级队列结构就是堆结构heapInsert 入堆排序操作从数组最后一个位置插入然后再与其父节点(i-1)/2比较大小大则交换上去接着往其爷节点持续走..直到顶或小于当前节点的父节点则停止完成排序heapify:堆下沉排序操作 剔除元素后需要将交换到根部的元素往下沉判断排序如果大于左右节点就不用动小于则与左右较大节点交换并下沉继续判断直到底部或者大于左右子节点代码演示package class06;import java.util.Comparator;
import java.util.PriorityQueue;public class Heap {//大根堆 每个子树根节点比左右节点大public static class MyMaxHeap {private int[] heap;private int heapSize;private final int limit;public MyMaxHeap(int limit) {heap new int[limit];heapSize 0;this.limit limit;}public boolean isEmpty() {return heapSize 0;}public boolean isFull() {return limit heapSize;}//入堆同时保持堆的大根堆 有序public void push(int value) {if (isFull()) {throw new RuntimeException(堆已满无法添加元素);}//没满就赋值追加到数组后heap[heapSize] value;//依次与该元素的父节点比较大小大则交换两元素然后接着往上走直到顶或者不大于父节点,同时最后要把size1heapInsert(heap, heapSize);}//入堆操作从数组最后一个位置插入然后再与其父节点(i-1)/2比较大小大则交换上去接着往其爷节点持续走..直到顶或小于当前节点的父节点则停止完成排序private void heapInsert(int[] heap, int i) {//这个条件判断了两种情况一个是大于父节点一个是还没到顶节点假如i来到顶部0 那么(i-1)/2也等0 为自己是等于 则继续循环。while (heap[i] heap[(i - 1) / 2]) {swap(heap, i, (i - 1) / 2);i (i - 1) / 2;}}//出堆弹出最大值顶部然后保证当前堆仍有序 是大根堆public int pop() {if (isEmpty()) {throw new RuntimeException(堆已空无法弹出元素);}//弹出首元素最大值int ans heap[0];//然后把元素剔除两步 1.将首元素与尾元素heapSize是长度尾元素是heapSize-1交换因为弹出操作需要将heapSize 元素个数-1两个操作只需要用--heapSize就能符合swap(heap, 0, --heapSize);//2.交换后表示将根节点元素剔除然后需要确保现有堆的顺序heapify(heap, 0, heapSize);return ans;}//堆下沉排序操作 剔除元素后需要将交换到根部的元素往下沉判断排序如果大于左右节点就不用动小于则与左右较大节点交换并下沉继续判断直到底部或者大于左右子节点private void heapify(int[] heap, int i, int heapSize) {//首先判断是否存在左子节点左节点索引是i*21,不能超过heapSize-1尾索引如果超过那肯定就到最后一个元素右节点是比左节点大1 也更不会存在while (i * 2 1 heapSize) {//此时确定有左节点但需要判断是否有右节点i*22 如果有 并且大于左节点那么左右节点较大值就是右节点否则就是左节点int largest i*22 heapSize heap[i*22]heap[i*21]?i*22:i*21;//然后把较大的节点与父节点比较谁大则重新赋值 largest最大值largest heap[largest] heap[i]?largest:i;if(largest i) break; //如果判断后这个最大值位置就是父节点位置相当于父节点都大于子节点那么就不用交换,再下沉此时已经完成排序大的仍旧在前面小的在下面直接退出循环//子节点大于当前节点那么与其较大的节点交换交换完之后当前节点i要来到较大节点largest位置 循环下沉swap(heap,i,largest);i largest;}}private void swap(int[] heap, int i, int j) {int temp heap[i];heap[i] heap[j];heap[j] temp;}}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 class MyComparator implements ComparatorInteger{Overridepublic int compare(Integer o1, Integer o2) {return o2-o1; //降序}}public static void main(String[] args) {// 大根堆 优先队列默认是小根堆通过比较器降序排序实现大根堆PriorityQueueInteger heap new PriorityQueue(new MyComparator());heap.add(5);heap.add(5);heap.add(5);heap.add(3);// 5 , 3System.out.println(heap.peek());heap.add(7);heap.add(0);heap.add(7);heap.add(0);heap.add(7);heap.add(0);System.out.println(heap.peek());while (!heap.isEmpty()) {System.out.println(heap.poll());}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)从上到下的方法时间复杂度为O(N*logN) 2)从下到上的方法时间复杂度为O(N) 2把堆的最大值和堆末尾的值交换然后减少堆的大小之后再去调整堆一直周而复始时间复杂度为O(N*logN) 3堆的大小减小成0之后排序完成手写堆结构来进行排序操作代码演示package class06;import java.util.Arrays;
import java.util.PriorityQueue;public class HeapSort {/*** 堆排序 利用堆的heapInsert heapify操作实现* param arr*/public static void heapSort(int[] arr){if(arr null || arr.length 2) return;//1.先使数组转换成一个大根堆heapInsert heapify都可以 后者的时间复杂度更低,从下往上 时间复杂度O(N)int heapSize arr.length;for(int i arr.length-1;i0;i--){heapify(arr,i,heapSize);}//O(N*logN)
// for(int i 0;iarr.length;i){
// heapInsert(arr,i);
// }//2、首位交换把最大值放到尾部因为排序我们按降序最大值就是放到尾部swap(arr,0,--heapSize);//3.依次开始进行堆下沉操作 直到排完序// O(N*logN)while(heapSize 0){ //O(N)heapify(arr,0,heapSize); //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 heapify(int[] arr, int i, int heapSize){int left i*21;while(left heapSize){int largest left 1 heapSize arr[left 1] arr[left]?left1:left;largest arr[largest] arr[i] ? largest : i;if(largest i) break;swap(arr,i,largest);i largest;left i*21;}}private static void swap(int[] arr, int i, int j) {int temp arr[i];arr[i] arr[j];arr[j] temp;}// for testpublic static void comparator(int[] arr) {Arrays.sort(arr);}// for testpublic 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 testpublic 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 testpublic 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 testpublic 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 testpublic static void main(String[] args) {// 默认小根堆PriorityQueueInteger 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);}
}
三、限定条件下堆排序假设每个元素移动的距离一定不超过k并且k相对于数组长度来说是比较小的题意已知一个几乎有序的数组。几乎有序是指如果把数组排好顺序的话每个元素移动的距离一定不超过k并且k相对于数组长度来说是比较小的。 请选择一个合适的排序策略对这个数组进行排序。 思路小根堆排序、优先队列题目中提到了一个每个元素移动的距离一定不超过k那么就说明从第一个数开始前k1个数里面存在一个数是一定要排在0位置的这样才能使得移动不超过k个 比如一个数组最小是1长度为8k5最小1是需要排在索引0位置的为了满足移动不超过5个位置那么在arr[0-k]区间内必然有1最远只能在rr[k],那么也是移动k为来到0 k-k0 ,利用这个特性用小根堆先把前k个数[0,k-1]入堆然后第二次开始从[k,arr.length-1]入堆入一次 就依次从头赋值给原数组然后再出堆比如前面例子第一次肯定是把1赋值给arr[0],出堆往后入堆赋值arr[1]出堆..直到最后一个元素最后可能堆还有元素就依次赋值给后面的数组位置依次出堆完成堆排序代码演示这里不手写堆结构一般都是直接用PriorityQueue优先队列默认小根堆排序说是优先队列其实也是堆结构实现的 package class06;import java.util.Arrays;
import java.util.PriorityQueue;/**题意* 已知一个几乎有序的数组。几乎有序是指如果把数组排好顺序的话每个元素移动的距离一定不超过k并且k相对于数组长度来说是比较小的。* 请选择一个合适的排序策略对这个数组进行排序。** 思路小根堆排序、优先队列题目中提到了一个每个元素移动的距离一定不超过k那么就说明从第一个数开始前k1个数里面存在一个数是一定要排在0位置的* 这样才能使得移动不超过k个 比如一个数组最小是1长度为8k5最小1是需要排在索引0位置的为了满足移动不超过5个位置那么在arr[0-k]* 区间内必然有1最远只能在rr[k],那么也是移动k为来到0 k-k0 ,利用这个特性用小根堆先把前k个数[0,k-1]入堆然后第二次开始从[k,arr.length-1]* 入堆入一次 就依次从头赋值给原数组然后再出堆比如前面例子第一次肯定是把1赋值给arr[0],出堆往后入堆赋值arr[1]出堆..直到最后一个元素* 最后可能堆还有元素就依次赋值给后面的数组位置依次出堆完成堆排序*/
public class SortArrayDistanceLessK {public static void sortArrayDistanceLessK(int[] arr, int k){if(arr null || arr.length 2) return;PriorityQueueInteger heap new PriorityQueue();//技巧把堆索引定义外面定义for里面的话就没法给后续的操作使用int index 0;//1.首先我们把0,k-1的区间先入堆下次开始入k时就时要开始循环赋值、出堆因为arr[k] 前面有k个数//题目限定每个元素移动不超过k 那么排在arr[0]的数肯定就是再0k区间内所以再k入堆时就可以出堆其//最小值就是位于arr[0]//判断最小值是因为我们测试用例的k范围是随机的可能会大于数组长度for(;index Math.min(arr.length-1,k);index){heap.add(arr[index]);}//2.此时index k ,开始往后遍历,index不超过数组长度 赋值出堆//定义数组从0开始的下标 用于赋值int indexArr 0;for(;indexarr.length;index,indexArr){heap.add(arr[index]);//出堆赋值出堆是因为该值已经赋值到数组了就需要排除arr[indexArr] heap.poll();}//3.此时遍历到最后堆可能还有元素需要依次再赋值到arr[indexArr]位置while(!heap.isEmpty()){arr[indexArr] heap.poll();}}// for testpublic static void comparator(int[] arr, int k) {Arrays.sort(arr);}// for testpublic 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 testpublic 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 testpublic 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 testpublic 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 testpublic 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);sortArrayDistanceLessK(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!);}}
