⭐️前言⭐️

本篇文章记录堆排序以及对应的一些练习。

🍉欢迎点赞 👍 收藏 ⭐留言评论 📝私信必回哟😁

🍉博主将持续更新学习记录收获，友友们有任何问题可以在评论区留言

🍉博客中涉及源码及博主日常练习代码均已上传GitHub

🍅1.堆排序实现

实现思路：
1.首先先建大堆
2.建好堆后，利用堆的性质完成排序
3.将堆顶元素与堆位元素互换，那么堆尾位置元素就是堆中的最大元素，并将堆顶元素向下调整，继续保持堆结构。
4.持续相同操作，直到到堆顶位置，此时堆中元素变为升序。

代码实现：

public class HeapSort {public static void heapSort(int[] array) {createBigHeap(array);int end=array.length-1;while (end>=0) {swap(array,0,end);shiftDown(array,0,end);end--;}}private static void shiftDown(int[] array,int parent,int len) {// 保证有左孩子int child=2*parent+1;while (child<len) {// 如果有右孩子，左右孩子比较，child记录较大值的下标if(child+1<len&&array[child]<array[child+1]) {child++;}if(array[child]>array[parent]) {swap(array,child,parent);// 继续向下调整parent=child;child=2*parent+1;}else {break;}}}private static void swap(int[] array,int i,int j) {int tmp=array[i];array[i]=array[j];array[j]=tmp;}private static void createBigHeap(int[] array) {// 先找到最后一棵子树的父节点，让每棵子树成为大顶堆for(int parent=(array.length-1-1)/2;parent>=0;parent--) {shiftDown(array,parent,array.length);}}
}

🍅2.线段最大重合问题

题目：
给定很多线段，每个线段都有两个数[start, end]，
表示线段开始位置和结束位置，左右都是闭区间
规定：
1）线段的开始和结束位置一定都是整数值
2）线段重合区域的长度必须>=1
返回线段最多重合区域中，包含了几条线段

题解思路：
1.首先通过比较器，将所有线段基于线段的起始位置进行排序，然后来求每条线段的最大重复线段数。
2.利用小根堆（小根堆存储每条线段的结束位置），每次到达新线段时，将小根堆中比新线段起始位置小的数弹出（弹出的线段是起始位置和结束位置都比新线段其实位置小的线段，不可能有重复），并将新线段的结束位置放入小根堆，此时小根堆中代表的线段就是有公共重合区域的线段，返回heap.size()就是重复线段数。
3.每条线段都进行这样的操作，返回heap.size()中最大的max，就表示线段最多重合区域中，包含的线段数。

代码实现：

public class CoverMax {static class Line {public int start;public int end;public Line(int start, int end) {this.start = start;this.end = end;}}static int maxCover(int[][] m) {Line[] lines=new Line[m.length];for (int i = 0; i < m.length; i++) {lines[i]=new Line(m[i][0],m[i][1]);}Arrays.sort(lines, new Comparator<Line>() {@Overridepublic int compare(Line o1, Line o2) {return o1.start-o2.start;}});// Arrays.sort(lines,(a,b)->a.start-b.start);  // 语法糖PriorityQueue<Integer> heap=new PriorityQueue<>();int max=0;for (int i = 0; i < lines.length; i++) {while (!heap.isEmpty()&&heap.peek()<=lines[i].start) {heap.poll();}heap.add(lines[i].end);max=Math.max(max,heap.size());}return max;}
}

🍅3.加强堆的实现

是对于普通堆结构的改写，增添了一些普通堆不具有的功能

public class HeapGreater<T> {private ArrayList<T> heap;private HashMap<T,Integer> indexMap;  // 用于加强堆结构中的反向索引操作private int heapSize;private Comparator<? super T> comp;public HeapGreater(Comparator<? super T> comp) {heap=new ArrayList<>();indexMap=new HashMap<>();heapSize=0;this.comp = comp;}// 判断堆是否为空public boolean isEmpty() {return heapSize==0;}// 返回堆大小public int size() {return heapSize;}// 判断堆中是否包含某个元素public boolean contains(T obj) {return indexMap.containsKey(obj);}// 返回堆顶元素public T peek() {return heap.get(0);}// 堆中新增元素public void push(T obj) {heap.add(obj);indexMap.put(obj,heapSize);heapInsert(heapSize);heapSize++;}// 堆中插入新元素，向上调整新元素private void heapInsert(int child) {int parent=(child-1)/2;while (child>0) {if(comp.compare(heap.get(child),heap.get(parent))<0) {swap(child,parent);child=parent;parent=(child-1)/2;}else {break;}}}private void swap(int i, int j) {T o1=heap.get(i);T o2=heap.get(j);heap.set(i,o2);heap.set(j,o1);indexMap.put(o2,i);indexMap.put(o1,j);}// 弹出堆顶元素public T pop() {T ans=heap.get(0);swap(0,heapSize-1);indexMap.remove(ans);heap.remove(--heapSize);shiftDown(0);return ans;}// 小根堆向下调整private void shiftDown(int parent) {int child=2*parent+1;while (child<heapSize) {if(child+1<heapSize&&comp.compare(heap.get(child+1),heap.get(child))<0) {child++;}if(comp.compare(heap.get(child),heap.get(parent))<0) {swap(child,parent);parent=child;child=2*parent+1;}else {break;}}}// 去除某个元素public void remove(T obj) {T replace=heap.get(heapSize-1);int index=indexMap.get(obj);indexMap.remove(obj);heap.remove(--heapSize);if(obj!=replace) {heap.set(index,replace);indexMap.put(replace,index);resign(replace);}}private void resign(T obj) {heapInsert(indexMap.get(obj));shiftDown(indexMap.get(obj));}// 返回堆上所有元素public List<T> getAllElements() {List<T> ans=new ArrayList<>();for(T c:heap) {ans.add(c);}return ans;} 
}

⭐️最后的话⭐️
总结不易，希望uu们不要吝啬你们的👍哟(＾Ｕ＾)ノ~ＹＯ！！如有问题，欢迎评论区批评指正😁