[LeetCode] 215. Kth Largest Element in an Array, Medium

1. 문제

• 정수 배열 nums와 정수 k가 주어질 때, 배열 내 k번째 큰 값을 구하라.

2. 해결

class MinHeap {
    private heap: number[];

    constructor() {
        this.heap = [];
    }

    getLeftChildIndex = (parentIndex) => parentIndex * 2 + 1;
    getRightChildIndex = (parentIndex) => parentIndex * 2 + 2;
    getParentIndex = (childIndex) => Math.floor((childIndex - 1) /2);

    swap = (i: number, j: number) => {
        [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
    };

    peek = () => this.heap[0];
    size = () => this.heap.length;

    push(value: number) {
        this.heap.push(value);
        this.heapifyUp();
    }

    heapifyUp() {
        let index = this.heap.length - 1; // 마지막 요소.

        while(index > 0 && this.heap[this.getParentIndex(index)] > this.heap[index]) { // 부모 노드보다 자식 노드가 작은 경우.
            this.swap(index, this.getParentIndex(index)); // 스왑.
            index = this.getParentIndex(index);
        }
    }

    pop(): number | undefined {
        if(this.heap.length === 0) return undefined;
        if(this.heap.length === 1) return this.heap.pop();

        const top = this.heap[0];
        this.heap[0] = this.heap.pop(); // 마지막 값을 root로 놓고.
        this.heapifyDown();

        return top;
    }

    heapifyDown() {
        let index = 0;
        
        while(this.getLeftChildIndex(index) < this.heap.length) { // 자식이 있는 경우 반복, left가 없으면 right도 없기 때문에.
            // 왼쪽, 오른쪽 중 더 작은 자식을 찾음. 최소 힙이므로.
            let smallerChildIndex = this.getLeftChildIndex(index);
            const rightChildIndex = this.getRightChildIndex(index);

            if(rightChildIndex < this.heap.length && this.heap[rightChildIndex] < this.heap[smallerChildIndex]) {
                smallerChildIndex = rightChildIndex;
            }

            if(this.heap[index] <= this.heap[smallerChildIndex]) break; // 현재 노드가 자식보다 작거나 같으면 종료.

            this.swap(index, smallerChildIndex);
            index = smallerChildIndex;
        }
    }
}

function findKthLargest(nums: number[], k: number): number {
    const heap = new MinHeap();

    for(const num of nums) {
        heap.push(num);

        if(heap.size() > k) heap.pop();
    }

    return heap.peek();
};

• 다른 방식으로 구현할 수 있겠지만, heap을 사용한 우선순위 큐도 공부해야 할 것 같아 추가했다.
• k번째 큰 수를 구하는 방법은 k크기를 유지하도록 최소 힙에 요소를 삽입하면 요소 내에는 k개의 숫자가 큰 순서대로 저장된다.
• 삽입 후 루트 노드를 반환하면 정답.