【算法数据结构体系篇class06】：堆、大根堆、小根堆、优先队列

一、堆结构

1）堆结构就是用数组实现的完全二叉树结构
2）完全二叉树中如果每棵子树的最大值都在顶部就是大根堆
3）完全二叉树中如果每棵子树的最小值都在顶部就是小根堆
4）堆结构的heapInsert与heapify操作
5）堆结构的增大add和减少poll
6）优先级队列结构，就是堆结构

• 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;//依次与该元素的父节点比较大小，大则交换两元素，然后接着往上走，直到顶或者不大于父节点,同时最后要把size+1heapInsert(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*2+1,不能超过heapSize-1尾索引，如果超过那肯定就到最后一个元素，右节点是比左节点大1 也更不会存在while (i * 2 + 1 < heapSize) {//此时确定有左节点，但需要判断是否有右节点i*2+2 如果有 并且大于左节点，那么左右节点较大值就是右节点，否则就是左节点int largest = i*2+2 < heapSize && heap[i*2+2]>heap[i*2+1]?i*2+2:i*2+1;//然后把较大的节点与父节点比较，谁大则重新赋值 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 Comparator<Integer>{@Overridepublic int compare(Integer o1, Integer o2) {return o2-o1; //降序}}public static void main(String[] args) {// 大根堆   优先队列默认是小根堆，通过比较器降序排序实现大根堆PriorityQueue<Integer> 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;i>=0;i--){heapify(arr,i,heapSize);}//O(N*logN)
//        for(int i = 0;i<arr.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*2+1;while(left < heapSize){int largest = left + 1 < heapSize && arr[left + 1] >arr[left]?left+1:left;largest = arr[largest] > arr[i] ? largest : i;if(largest == i) break;swap(arr,i,largest);i = largest;left = i*2+1;}}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) {// 默认小根堆PriorityQueue<Integer> 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，那么就说明，从第一个数开始，前k+1个数里面，存在一个数，是一定要排在0位置的，这样才能使得移动不超过k个， 比如一个数组最小是1，长度为8，k=5，最小1是需要排在索引0位置的，为了满足移动不超过5个位置，那么在arr[0-k]区间内必然有1，最远只能在rr[k],那么也是移动k为来到0 k-k=0 ,利用这个特性，用小根堆，先把前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，那么就说明，从第一个数开始，前k+1个数里面，存在一个数，是一定要排在0位置的* 这样才能使得移动不超过k个， 比如一个数组最小是1，长度为8，k=5，最小1是需要排在索引0位置的，为了满足移动不超过5个位置，那么在arr[0-k]* 区间内必然有1，最远只能在rr[k],那么也是移动k为来到0 k-k=0 ,利用这个特性，用小根堆，先把前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;PriorityQueue<Integer> heap = new PriorityQueue<>();//技巧：把堆索引定义外面，定义for里面的话就没法给，后续的操作使用int index = 0;//1.首先我们把0,k-1的区间先入堆，下次开始入k时，就时要开始循环赋值、出堆，因为arr[k] 前面有k个数，//题目限定每个元素移动不超过k ，那么排在arr[0]的数，肯定就是再0，k区间内，所以再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(;index<arr.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!");}}