Given an integer array nums and an integer k, return the kth largest element in the array.
Note that it is the kth largest element in the sorted order, not the kth distinct element.
Can you solve it without sorting?

給定一個整數陣列 nums 以及一個整數 k，回傳陣列中第 k 大的元素。
注意要回傳的元素必須是在陣列 nums 中，經過排序後第 k 大的元素，而不是第 k 個不同的元素。
(這邊強調是排序後第k個大的元素，所以如果有重複的元素，也必須算進k裡面，詳見下面範例。)

你能夠在不排序陣列的情況下解決這道題目嗎?

進入到第十七天，我感覺這不是場馬拉松，是一條天堂路。

這道題有很多種解法，可以使用Bruce Force、也可以Quick Select，那既然前面學了Heap Sort，且題目也提到"能否不使用排序"解決問題，下面就針對Heap Sort的解法進行說明記錄囉!

[Concept]
先建立一個可以容納k個元素的min-heap，heapify後，由小至大排列，再與陣列中其他的元素比較，找出第k大的元素。

先把heapify做出來，這邊的heapify是min-heap，也就是heapify的過程就是不斷的把較大的值往heap的底部交換。

function heapify(arr, i = 0, value = arr[i]) {
    //left child 的索引值為 2n+1
    //right child 的索引值為 2n+2
    //left child 大於 right child
    
    while (true) {
        // i 是當前節點的index
        let j = i * 2 + 1;// 子節點(left child)
        
        //只要right child在陣列長度內 且 left child 比 right child大
        if (j+1 < arr.length && arr[j] > arr[j+1]){
            j++; //往heap下層移動
        }
        
        //如果child超出array長度 或 value比當前的child還要小 則結束while loop 表示已經找到位置了
        if (j >= arr.length || value <= arr[j]) break;
        
        //子節點換到當前節點
        arr[i] = arr[j];
        
        //更新當前節點index,繼續往下檢查
        i = j;
    }
    //while迴圈結束，把value值放入arr[i]的位置
    arr[i] = value;
}

因為要找到第 k 大，從上面heapify的結果會是由小至大排列，所以在這邊的for loop必須反著做，從陣列最後開始heapify，這樣最後heap sort的結果才會是由大排到小。

//建立heap
function buildHeap(arr) {
    const lastIndex = Math.floor((arr.length - 1) / 2);
    //從陣列最後的index開始進行heapify
    for (let i = lastIndex; i >= 0; i--) {
        heapify(arr, i);
    }
    return arr;
}

最後總結以上function:
建立heap，heap裡面只有k個元素，再利用for loop從陣列 nums 的第k個索引值跟heap的根節點(root)比較，只要比根節點大，就要重新heapify。

function findKthLargest(nums, k) {
    const heap = buildHeap(nums.slice(0, k));
    for (let i = k; i < nums.length; i++) {
        //只要nums[i]比root大，則重新heapify
        if (nums[i] > heap[0]) heapify(heap, 0, nums[i]);
    }
    return heap[0];
}

為什麼最後返回的heap[0]會是第k大的元素呢?
因為在一開始建立的heap中，就已經確保了k個位置(也就是可以容納k個元素)，那麼在for loop的過程中，只有比根節點大的元素，才有機會進入heap，所以最後能在每一次的比較中勝出得元素，才能在heap中留到最後，這也代表了最後min-heap裡面的最小元素heap[0]，會是陣列nums中第k大的元素。

Reference:
https://stackoverflow.com/questions/56737090/kth-largest-element-in-an-array