找出亂序數組第k大的數字（堆排序專場）

使用堆排序來解決《亂序數組第k大的數字》
先放上代碼（雖然leetcode要求O(n)，但是堆排序是O(nlogn)）
`class Solution {
public int findKthLargest(int[] nums, int k) {
int heapSize = nums.length;
buildHeap(nums, heapSize);
for(int i = nums.length - 1; i >= nums.length - k + 1; i--) {
swap(nums, 0, i);
heapSize--;
buildHeap(nums, heapSize);
}
return nums[0];
}

public void buildHeap(int[] nums, int heapSize) {
    for(int i = heapSize / 2 - 1; i >= 0; i--) {
        maximum(nums, i, heapSize);
    }
}

public void maximum(int[] nums, int root, int heapSize) {
    int lChild = root * 2 + 1;
    int rChild = root * 2 + 2;
    int largest = root;

    if (lChild < heapSize && nums[lChild] > nums[largest]) {
        largest = lChild;
    }
    if (rChild < heapSize && nums[rChild] > nums[largest]) {
        largest = rChild;
    }
    // 如果largest不再是入參那個根節點，說明有子節點比它大，要換，換了之後繼續往下遞歸看還有沒有
    if (largest != root) {
        swap(nums, root, largest);
        maximum(nums, root, largest);
    }
}

public void swap(int[] nums, int a, int b) {
    int temp = nums[a];
    nums[a] = nums[b];
    nums[b] = temp;
}

}`

比較有收穫的幾個點：

• 堆裡面兒子節點是父親節點n的n2+1和n2+2
• 刪除堆的堆頂是通過把堆頂元素和堆最後的元素交換，並且heapSize--來實現的
• 如果有兒子節點比父親節點大，那麼需要交換父親節點和這個兒子節點，並且繼續將交換之後新的兒子節點作為新的根節點往下遞歸判斷
• 可以從heapSize/2這個節點開始判斷，並不斷--，最後得到的數組[0]就是正確的堆頂，進行進一步處理即可