잘못된 접근

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findKthLargest = function(nums, k) {
    // 결국에는 중구난방의 배열 원소를 k를 사용할 수 있도록 정렬해줄 필요가 있다.
    // 그런데 정렬을 사용할 수 없다.
    // Heapify를 통해 배열을 Max Heap 형태로 전환하고 k번째 원소를 얻으면 되지 않을까?
    // Heapify의 문제점 - 배열을 트리로 바꾸는 과정에서 특정 노드의 자식으로만 남아있기 때문에
    // k번째 큰 수가 반드시 k번째에 있지 않게 된다.

    function heapify(){
        // 리프 노드가 아닌 노드 중에서 가장 낮은 인덱스를 가지는 노드부터 점점 위로 올라간다.
        for(let i = Math.floor((nums.length - 2) / 2); i >= 0; i--){
            // 왼쪽 자식 노드가 더 큰 경우
            if(nums[i] < nums[2*i + 1]){
                swap(nums, i, 2*i + 1);
                heapify();
            }

            // 오른쪽 자식 노드가 더 큰 경우
            if(nums[i] < nums[2*i + 2]){
                swap(nums, i, 2*i + 2);
                heapify();
            }
        }
    }

    heapify();

    return nums[k - 1];
};

function swap(arr, parentIdx, childIdx){
    const temp = arr[parentIdx];
    arr[parentIdx] = arr[childIdx];
    arr[childIdx] = temp;
}

Heap 관련 문제라는 것을 보고는 Heapify를 통해 문제를 해결하는 건가 싶었다.
그러나, 테스트 케이스를 보면 이게 틀린 방법이라는 것을 알 수 있었다.
Heapify를 통해 Max Heap을 만들었지만, 가장 큰 문제는 Heap이 된 상태에서 그를 배열로 표현해도,
k번째 숫자가 실제로 k번째로 큰 숫자가 되지는 않는다는 것이다.
문제에서 원하는 것은 k번째로 큰 숫자인 것이지, k번 노드에 있는 숫자가 아니다!

여기서 필자가 착각한 것이 있다. nums로 주어진 배열은 그 어떤 특징도 가지고 있지 않다.
nums가 완전 이진 트리를 배열로 변경해놓은 것이라고 생각하고 있었는데, 그게 아니었다.
즉, nums는 아무것도 아닌 평범한 배열이고, 이를 Heap으로 전환하면 앞서 말한 문제점이 전부 해결된다.
nums를 완전 이진 트리를 나타내는 배열이라고 생각해버린 것이 원인이었다.

Time Limit Exceeded

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findKthLargest = function(nums, k) {
    heapify(nums);

    for(let i = 0; i < k - 1; i++){
        nums[0] = nums[nums.length - 1];
        nums.pop();
        heapify(nums);
    }

    return nums[0];
};

function heapify(arr){
    // 리프 노드가 아닌 노드 중에서 가장 낮은 인덱스를 가지는 노드부터 점점 위로 올라간다.
    for(let i = Math.floor((arr.length - 2) / 2); i >= 0; i--){
        // 왼쪽 자식 노드가 더 큰 경우
        if(arr[i] < arr[2*i + 1]){
            swap(arr, i, 2*i + 1);
            heapify(arr);
        }
        // 오른쪽 자식 노드가 더 큰 경우
        if(arr[i] < arr[2*i + 2]){
            swap(arr, i, 2*i + 2);
            heapify(arr);
        }
    }
}

function swap(arr, parentIdx, childIdx){
    [arr[childIdx], arr[parentIdx]] = [arr[parentIdx], arr[childIdx]];
}

이번에는 잘못된 접근을 해결하기 위해서 Max Heap에서 최댓값인 root를 제거해나가며 Heapify를 하는 방법을 사용했다.
Max Heap에서 root를 제거한 뒤, 다시 Heapify를 해서 Max Heap으로 만드는 과정을
k - 1번만큼 반복하면, k번째로 큰 숫자를 root로 가지는 Heap이 완성된다.

문제는, 필자의 heapify()가 시간 복잡도가 상당한 것으로 생각된다.
재귀를 사용하긴 했는데, 불필요한 재귀를 하는 경우가 있다는 것을 확인하였다.
이를 개선하면 테스트 케이스를 전부 통과할 수 있을 것으로 생각된다.

solution

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findKthLargest = function(nums, k) {
    heapify(nums);

    for(let i = 0; i < k - 1; i++){
        nums[0] = nums[nums.length - 1];
        nums.pop();
        bubbleDown(nums, 0);
    }

    return nums[0];
};

function heapify(arr){
    // 리프 노드가 아닌 노드 중에서 가장 낮은 인덱스를 가지는 노드부터 점점 위로 올라간다.
    for(let i = Math.floor((arr.length - 2) / 2); i >= 0; i--){
        bubbleDown(arr, i);
    }
}

function bubbleDown(arr, index){
    const leftChildIndex = 2 * index + 1;
    const rightChildIndex = 2 * index + 2;
    let greaterIndex = index;

    // 왼쪽 자식 노드가 더 큰 경우
    if(arr[greaterIndex] < arr[leftChildIndex]){
        greaterIndex = leftChildIndex;
    }

    // 오른쪽 자식 노드가 더 큰 경우
    if(arr[greaterIndex] < arr[rightChildIndex]){
        greaterIndex = rightChildIndex;
    }

    if(greaterIndex !== index){
        swap(arr, index, greaterIndex);

        bubbleDown(arr, greaterIndex);
    }

}

function swap(arr, parentIdx, childIdx){
    [arr[childIdx], arr[parentIdx]] = [arr[parentIdx], arr[childIdx]];
}

heapify()에서 불필요한 재귀가 발생하는 것을 억제하기 위해,
변경이 발생하는 인덱스를 체크하고 bubbleDown()을 실행하도록 변경했다.
heapify()는 초기 Heap을 생성하는 용도이고, 그 후로 Heap을 변경해야한다면 bubbleDown을 사용하는 방식이다.
heapify()를 사용해도 문제는 해결이 되겠지만, for문을 전체적으로 다시 실행해야한다는 점이 시간 복잡도를 늘렸던 원인이므로, 이를 최대한 회피하는 것이 좋다고 판단했다.

또한, pop() 부분의 로직에서도 heapify()가 아니라 bubbleDown()을 사용하며,
이 때, index를 0으로 설정하여 최상단부터 다시 재정렬이 되도록 했다.
heapify()를 반복하느냐, bubbleDown()을 반복하느냐의 차이로 시간 제한 문제를 해결할 수 있었다.

다른 분의 solution

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findKthLargest = function(nums, k) {
    const maxHeap = new MaxHeap(nums);
    for (let i = 0; i < k - 1; i++) {
        maxHeap.pop();
    }
    return maxHeap.top();
}

class MaxHeap {
    constructor(nums) {
        this.heap = nums;
        this.buildHeap();
    }
    
    buildHeap() {
        for (let i = Math.floor(this.heap.length / 2) - 1; i >= 0; i--) {
            this.shiftDown(i);
        }
    }
    
    shiftDown(index) {
        const leftChildIndex = 2 * index + 1;
        const rightChildIndex = 2 * index + 2;
        let maxIndex = index;
        
        if (leftChildIndex < this.heap.length && this.heap[leftChildIndex] > this.heap[maxIndex]) {
            maxIndex = leftChildIndex;
        }
        
        if (rightChildIndex < this.heap.length && this.heap[rightChildIndex] > this.heap[maxIndex]) {
            maxIndex = rightChildIndex;
        }
        
        if (maxIndex !== index) {
            [this.heap[index], this.heap[maxIndex]] = [this.heap[maxIndex], this.heap[index]];
            this.shiftDown(maxIndex);
        }
    }
    
    pop() {
        [this.heap[0], this.heap[this.heap.length - 1]] = [this.heap[this.heap.length - 1], this.heap[0]];
        const maxElement = this.heap.pop();
        this.shiftDown(0);
        return maxElement;
    }
    
    top() {
        return this.heap[0];
    }
}

이 분은 class 문법을 사용하셨다.
this를 통해서 내부에서 전역적으로 변수에 접근 가능한 점이 함수를 더 깔끔하게 만들어준다.
로직은 필자와 동일하다.
필자가 구현한 것이 Heap 문제를 해결하는 전형적인 로직이었던 것 같다.