0703-kth-largest-element-in-a-stream.ts

class KthLargest {
    backingArray: number[];
    size: number;

    constructor(k: number, nums: number[]) {
        this.backingArray = [];
        this.size = k;
        for(const num of nums) this.add(num)
    }

    add(val: number): number {
        const newLength = this.backingArray.push(val)
        this.shiftUp(newLength - 1);

        if (newLength > this.size) this.pop();

        return this.backingArray[0];
    }

    private pop() {
        this.swap(0, this.backingArray.length - 1)
        this.backingArray.length -= 1;
        this.shiftDown(0)
    }

    private shiftDown(elementIndex: number) {
        let leftChildIndex = elementIndex * 2 + 1;
        let rightChildIndex = elementIndex * 2 + 2;

        while ((leftChildIndex < this.backingArray.length && this.backingArray[leftChildIndex] < this.backingArray[elementIndex])
        || (rightChildIndex < this.backingArray.length && this.backingArray[rightChildIndex] < this.backingArray[elementIndex])) {
            let smallestIndex = leftChildIndex;
            if (rightChildIndex < this.backingArray.length && this.backingArray[rightChildIndex] < this.backingArray[smallestIndex]) {
                smallestIndex = rightChildIndex
            }

            this.swap(elementIndex, smallestIndex);

            elementIndex = smallestIndex;
            leftChildIndex = elementIndex * 2 + 1;
            rightChildIndex = elementIndex * 2 + 2;
        }
    }

    private shiftUp(elementIndex: number) {
        if (elementIndex === 0) return;

        let parentIndex = Math.floor((elementIndex - 1) / 2);
        while (this.backingArray[parentIndex] > this.backingArray[elementIndex]) {
            this.swap(elementIndex, parentIndex);
            elementIndex = parentIndex;
            parentIndex = Math.floor((elementIndex - 1) / 2);
        }
    }

    private swap(indexA: number, indexB: number) {
        const temp = this.backingArray[indexA];
        this.backingArray[indexA] = this.backingArray[indexB];
        this.backingArray[indexB] = temp;
    }
}