Learning Journal

2/6/2024

Smallest Number in Infinitive Set - 2nd attempt

class SmallestInfiniteSet {
    private curInt:number = 1;
    private addedInts = new MinPQ();
    private isPresent = new HashSet();

    popSmallest():number {
        if(!this.addedInts.isEmpty()) {
            const val = this.addedInts.pop();
            this.isPresent.remove(val);

            return val;
        }

        this.curInt++;

        return this.curInt - 1;
    }

    addBack(num:number):void {
        if(num >= this.curInt || this.isPresent.contains(num)) return;

        this.addedInts.add(num);
        this.isPresent.add(num);
    }
}

class MinPQ {
    private arr:number[] = [];

    isEmpty():boolean {
        return this.arr.length === 0;
    }

    pop():number {
        // this.arr can be empty
        if(this.isEmpty()) throw new Error("Heap is empty");

        // this.arr.length can be equal to 1
        const val = this.arr[0];

        const last = this.arr.pop();
        if(this.isEmpty()) return val;

        // now this.arr.length >= 1

        this.arr[0] = last;

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

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

            this.swap(curI, smallerChildI);

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

        return val;
    }

    add(num:number):void {
        this.arr.push(num);

        let curIndex = this.arr.length - 1;
        let parentIndex = this.getParentI(curIndex);

        while(curIndex > 0 && this.arr[curIndex] < this.arr[parentIndex]) {
            this.swap(curIndex, parentIndex);
            curIndex = parentIndex;
            parentIndex = this.getParentI(curIndex);
        }
    }

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

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

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

    private swap(i:number, j:number):void {
        const temp = this.arr[i];
        this.arr[i] = this.arr[j];
        this.arr[j] = temp;
    }
}

class HashSet {
    private hashTB: Record<number, boolean> = {};

    remove(val:number):void {
        delete this.hashTB[val];
    }

    add(num:number):void {
        this.hashTB[num] = true;
    }

    contains(num:number):boolean {
        return this.hashTB[num];
    }
}class SmallestInfiniteSet {
    private curInt:number = 1;
    private addedInts = new MinPQ();
    private isPresent = new HashSet();

    popSmallest():number {
        if(!this.addedInts.isEmpty()) {
            const val = this.addedInts.pop();
            this.isPresent.remove(val);

            return val;
        }

        this.curInt++;

        return this.curInt - 1;
    }

    addBack(num:number):void {
        if(num >= this.curInt || this.isPresent.contains(num)) return;

        this.addedInts.add(num);
        this.isPresent.add(num);
    }
}

class MinPQ {
    private arr:number[] = [];

    isEmpty():boolean {
        return this.arr.length === 0;
    }

    pop():number {
        // this.arr can be empty
        if(this.isEmpty()) throw new Error("Heap is empty");

        // this.arr.length can be equal to 1
        const val = this.arr[0];

        const last = this.arr.pop();
        if(this.isEmpty()) return val;

        // now this.arr.length >= 1

        this.arr[0] = last;

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

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

            this.swap(curI, smallerChildI);

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

        return val;
    }

    add(num:number):void {
        this.arr.push(num);

        let curIndex = this.arr.length - 1;
        let parentIndex = this.getParentI(curIndex);

        while(curIndex > 0 && this.arr[curIndex] < this.arr[parentIndex]) {
            this.swap(curIndex, parentIndex);
            curIndex = parentIndex;
            parentIndex = this.getParentI(curIndex);
        }
    }

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

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

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

    private swap(i:number, j:number):void {
        const temp = this.arr[i];
        this.arr[i] = this.arr[j];
        this.arr[j] = temp;
    }
}

class HashSet {
    private hashTB: Record<number, boolean> = {};

    remove(val:number):void {
        delete this.hashTB[val];
    }

    add(num:number):void {
        this.hashTB[num] = true;
    }

    contains(num:number):boolean {
        return this.hashTB[num];
    }
}

In the pop function, there are two corner cases.

The first one is when this.arr is empty. Because it is empty, the assignment const val = this.arr[0] will throw an error. Thus, we need to check it first. The second one is when this.arr has only 1 element. If it does, after the statement const last = this.arr.pop(), there must be nothing in the heap, but if there is no check on it, the statement this.arr[0] = last will assign the last element back to the heap, which is wrong.

Revised by ChatGPT

Handling Corner Cases in the pop Function of MinPQ:

When implementing the pop function in a Min Priority Queue, it's crucial to meticulously handle corner cases to ensure the integrity of the heap structure and avoid errors. Two specific corner cases need attention:

Empty Heap Scenario: When the heap (this.arr) is empty, attempting to access this.arr[0] would result in accessing an undefined element, leading to incorrect behavior or errors. Therefore, it's essential to check if the heap is empty at the beginning of the function. If the heap is empty, an error or a specific behavior should be defined, such as throwing an exception to indicate that there are no elements to pop.
Single Element Scenario: When the heap contains only one element, calling pop should remove and return this single element, leaving the heap empty. After popping this element, if we don't check for the heap's emptiness and proceed to reassign the last element to this.arr[0], it would erroneously reintroduce the popped element back to the heap. To prevent this, a check is performed after popping the last element. If the heap is found empty (indicating it had only one element), the function returns the popped value immediately, ensuring the heap remains correctly empty.

By addressing these corner cases, the pop function maintains the heap's integrity, ensuring that the minimum element is returned accurately, and the heap structure is preserved after removal.