现在进一步实现堆排序：
package heap04; /** * @author Corley * @date 2021/10/12 20:16 * @description LeetCodeAlgorithmZuo-heap04 */ public class HeapSort { /* 新加进来的数，现在停在了index位置，请依次往上移动 */ private void heapInsert(int[] arr, int index) { while (arr[index] > arr[(index - 1) / 2]) { swap(arr, index, (index - 1) / 2); } } public void swap(int[] arr, int i, int j) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } /* 从index位置，往下看，不断的下沉 停：较大的子节点都不再比index位置的数大；已经没子节点 */ public void heapify(int[] arr, int index, int heapSize) { int left = 2 * index + 1; while (left < heapSize) { int largest = left + 1 < heapSize && arr[left] < arr[left + 1] ? left + 1 : left; largest = arr[largest] > arr[index] ? largest : index; if (largest == index) { break; } swap(arr, largest, index); index = largest; left = 2 * index + 1; } } /* * 堆排序 * */ public void heapSort(int[] arr) { if (null == arr || arr.length < 2) { return; } for (int i = 0; i < arr.length; i++) { heapInsert(arr, i); } int heapSize = arr.length; swap(arr, 0, --heapSize); while (heapSize > 0) { heapify(arr, 0, heapSize); swap(arr, 0, --heapSize); } } }
现在分析时间复杂度：
建堆时，调用heapInsert(arr, i)方法N次，时间复杂度为O(N*LogN)，while循环也是O(N*LogN)，整体时间复杂度也是O(N*LogN)。
如果只是将数组变成大根堆，而不一定数组有序，可以优化为O(N)的时间复杂度，如下：
实现如下：
public void heapSort(int[] arr) { if (null == arr || 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); } }
现在进行证明，时间复杂度为O(N)：
堆排序的优势：
堆排序实现了O(N*LogN)的时间复杂度，但是只使用了有限的几个变量，达到了空间复杂度O(1)。
综上，堆排序：
1，先让整个数组都变成大根堆结构，建立堆的过程:
1）从上到下的方法heapinsert，时间复杂度为O(N*logN)；
2）从下到上的方法heapify，时间复杂度为O(N)。
直观说明如下：
2，把堆的最大值和堆末尾的值交换，然后减少堆的大小之后，再去调整堆。一直周而复始，时间复杂度为O(N*logN)
3，堆的大小减小成0之后，排序完成
现在实现使用系统的堆：
package heap04; import java.util.PriorityQueue; /** * @author Corley * @date 2021/10/13 14:56 * @description LeetCodeAlgorithmZuo-heap04 */ public class HeapUse { public static void main(String[] args) { PriorityQueue<Integer> heap = new PriorityQueue<>(); heap.add(5); heap.add(7); heap.add(3); heap.add(0); heap.add(5); heap.add(2); while (!heap.isEmpty()) { System.out.println(heap.poll()); } } }
优先队列的底层就是堆，默认是小根堆。
与堆有关的题目：
已知一个几乎有序的数组。几乎有序是指，如果把数组排好顺序的话，每个元素移动的距离一定不超过k，并且k相对于数组长度来说是比较小的。
请选择一个合适的排序策略,对这个数组进行排序。
分析：
方式是准备一个k+1大小的堆，放入
实现如下：
package heap04; import java.util.PriorityQueue; /** * @author Corley * @date 2021/10/13 15:12 * @description LeetCodeAlgorithmZuo-heap04 */ public class SortArrayDistanceLessK { public static void SortedArrayDistanceLessK(int[] arr, int k) { if (0 == k) { return; } // 小根堆 PriorityQueue<Integer> heap = new PriorityQueue<>(); int index = 0; for (; index <= k; index++) { heap.add(arr[index]); } int i = 0; for (; index < arr.length; i++, index++) { arr[i] = heap.poll(); heap.add(arr[index]); } while (!heap.isEmpty()) { arr[i++] = heap.poll(); } } }
复杂度为：O(N*LogK)。
