LEARNING JOURNAL

function topKFrequent(nums: number[], k: number): number[] {
    const hashTB:Record<string, number> = {};

    for(let i = 0; i < nums.length; i++) {
        if(hashTB[nums[i]] === undefined) {
            hashTB[nums[i]] = 1;
        }
        else 
            hashTB[nums[i]]++;
    }

    const maxHeap = new MaxHeap(hashTB);

    const result:number[] = [];

    for(let i = 0; i < k; i++){
        result.push(maxHeap.pop());
    }

    return result;
};


class MaxHeap {
    private arr: [number, number][] = [];
    readonly NUM:number = 0;
    readonly FREQUENCY:number = 1;

    constructor(hashTB:Record<string,number>) {
        const keys = Object.keys(hashTB);
        
        for(let i = 0; i < keys.length; i++) {
            this.push([Number(keys[i]), hashTB[keys[i]]])
        }

    }

    private swap(i1:number, i2:number) {
        const temp = this.arr[i1];
        this.arr[i1] = this.arr[i2];
        this.arr[i2] = temp;
    }

    private getParentI(i:number) {
        return Math.floor((i - 1)/2);
    }

    private getLeftChildI(i:number) {
        return 2*i + 1;
    }

    private getRightChildI(i:number) {
        return 2*i + 2;
    }

    push(item:[number,number]){
        this.arr.push(item);

        let curI = this.arr.length - 1, parentI = this.getParentI(curI);

        while(curI > 0 && this.arr[curI][this.FREQUENCY] > this.arr[parentI][this.FREQUENCY]){
            this.swap(curI, parentI);        
            curI = parentI;
            parentI = this.getParentI(curI);
        }
    }


    pop():number {
        if(this.arr.length === 0) throw new Error("The heap is empty");

        const retVal = this.arr[0][this.NUM];
        const last = this.arr.pop();

        if(this.arr.length === 0) return retVal;

        this.arr[0] = last;
        let curI = 0;

        let leftChildI = this.getLeftChildI(curI), rightChildI = this.getRightChildI(curI);

        while((leftChildI < this.arr.length && this.arr[curI][this.FREQUENCY] < this.arr[leftChildI][this.FREQUENCY])
            || (rightChildI < this.arr.length && this.arr[curI][this.FREQUENCY] < this.arr[rightChildI][this.FREQUENCY])
        ) {
            const largerChildI = rightChildI < this.arr.length && this.arr[rightChildI][this.FREQUENCY] > this.arr[leftChildI][this.FREQUENCY] ?
                                        rightChildI : leftChildI;

            this.swap(curI, largerChildI);

            curI = largerChildI;
            leftChildI = this.getLeftChildI(curI);
            rightChildI = this.getRightChildI(curI);    
        }


        return retVal;       
    }
}