【算法】排序算法之堆排序 - 知乎

應用場景：獲取第n個大或者小的數

操作步驟：

1、將數組構造成堆
2、調整根節點為最大堆

????????->倒序對每個根節點執行最大化

????????->根節點最大化過程中如果發生交換，需要保證子節點也為最大堆（執行最大堆）

class Solution {public int findKthLargest(int[] nums, int k) {int heapSize = nums.length;buildMaxHeap(nums, heapSize);for (int i = nums.length - 1; i >= nums.length - k + 1; --i) {swap(nums, 0, i);--heapSize;maxHeapify(nums, 0, heapSize);}return nums[0];}public void buildMaxHeap(int[] a, int heapSize) {for (int i = heapSize / 2 - 1; i >= 0; --i) {maxHeapify(a, i, heapSize);} }public void maxHeapify(int[] a, int i, int heapSize) {int l = i * 2 + 1, r = i * 2 + 2, largest = i;if (l < heapSize && a[l] > a[largest]) {largest = l;} if (r < heapSize && a[r] > a[largest]) {largest = r;}if (largest != i) {swap(a, i, largest);maxHeapify(a, largest, heapSize);}}public void swap(int[] a, int i, int j) {int temp = a[i];a[i] = a[j];a[j] = temp;}
}