一、堆排是个非常重要的排序算法了，也能够牵扯到很多其他方面的知识
先看代码
1 public static void heapSort(int[] arr) { 2 if (arr == null || arr.length < 2) { 3 return; 4 } 5 for (int i = 0; i < arr.length; i++) { 6 heapInsert(arr, i); 7 } 8 int size = arr.length; 9 swap(arr, 0, --size); 10 while (size > 0) { 11 heapify(arr, 0, size); 12 swap(arr, 0, --size); 13 } 14 } 15 16 public static void heapInsert(int[] arr, int index) { 17 while (arr[index] > arr[(index - 1) / 2]) { 18 swap(arr, index, (index - 1) / 2); 19 index = (index - 1) / 2; 20 } 21 } 22 23 public static void heapify(int[] arr, int index, int size) { 24 int left = index * 2 + 1; 25 while (left < size) { 26 int largest = left + 1 < size && arr[left + 1] > arr[left] ? left + 1 : left; 27 largest = arr[largest] > arr[index] ? largest : index; 28 if (largest == index) { 29 break; 30 } 31 swap(arr, largest, index); 32 index = largest; 33 left = index * 2 + 1; 34 } 35 } 36 37 public static void swap(int[] arr, int i, int j) { 38 int tmp = arr[i]; 39 arr[i] = arr[j]; 40 arr[j] = tmp; 41 }
其实，主要就是heapinsert和heapify的过程，先遍历一遍建堆，然后调整得到排序的数组
二、应用
1.top k问题
思路：建立一个k大小的小根堆，size小于k的时候往里面放，等于了的话就比较当前数与堆顶元素的大小，大于堆顶元素的话，就与堆顶元素替换，然后堆再调整为小 根堆，最后，遍历完数组，堆里面就是top元素。
2.在java中优先队列就是基于堆实现的，priorityQueue，默认是建立的小根堆,可以自己定义一个比较器，作为priorityQueue的参数，实现大根堆。
3.实时中位数问题：给定数组，计算出每个（0~i）时的中位数如[2,3,5,4,6,7],要分别计算[2],[2,3],[2,3,5],[2,3,5,4],[2,3,5,4,6],[2,3,5,4,6,7]的中位数
思路：如果每次都对前i个数排序，再求中位数，复杂度过高，太麻烦。可以建立两个堆，一个大根堆，一个小根堆。如果比大根堆堆顶小，入大根堆，否则入小根堆。在这个过程中，保证两个堆大小相差不超过1，超过的时候就向对方弹出自己的堆顶。这样，每次的中位数就能保证为，两个堆顶的一个，在根据两个堆的大小取舍。
形象来说就是建立两个三角形，一个在下面正着放，另一个在上面倒着放，这样中间顶点对立的位置就是中位数
1 public static ArrayList<Integer> getMedian(int [] A){ 2 ArrayList<Integer> ans = new ArrayList<>(); 3 if(A.length == 0) 4 return ans; 5 PriorityQueue<Integer> queue2 = new PriorityQueue<>(); 6 PriorityQueue<Integer> queue1 = new PriorityQueue<>(new MyComparator()); 7 int len = A.length; 8 queue1.add(A[0]); 9 ans.add(A[0]); 10 for(int i = 1;i < len;i++){ 11 if(A[i] <= queue1.peek()){ 12 queue1.add(A[i]); 13 } 14 else{ 15 queue2.add(A[i]); 16 } 17 if(queue1.size() - queue2.size()>1){ 18 queue2.add(queue1.poll()); 19 } 20 else if(queue2.size() - queue1.size() > 1){ 21 queue1.add(queue2.poll()); 22 } 23 if(queue2.size() > queue1.size()) 24 ans.add(queue2.peek()); 25 else 26 ans.add(queue1.peek()); 27 } 28 return ans; 29 } 30 static class MyComparator implements Comparator<Integer>{ 31 @Override 32 public int compare(Integer I1,Integer I2){ 33 return I2 - I1; 34 } 35 }
原文：https://www.cnblogs.com/ycf5812/p/10826935.html
