Learning Journal

2/7/2024

Smallest Number in Infinite Set - 3rd attempt

class SmallestInfiniteSet {
    private heap = new MinHeap();
    private set = new HashSet();
    private curInt = 1;

    popSmallest():number {
        if(!this.heap.isEmpty()){
            const val = this.heap.pop();
            this.set.remove(val);
            return val;
        }

        return this.curInt++;
    }

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

        this.heap.add(num);
        this.set.add(num);
    }
}

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

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

    pop():number {
        const val = this.arr[0];
        const last =  this.arr.pop();

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

        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 smallestChildI = rightChildI >= this.arr.length || this.arr[rightChildI] > this.arr[leftChildI]? leftChildI: rightChildI;

                   this.swap(smallestChildI, curI);
                        curI = smallestChildI;
                        leftChildI = this.getLeftChildI(curI);
                        rightChildI = this.getRightChildI(curI);
                }

        return val;
    }

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

        let curI = this.arr.length - 1;
        let parentI = this.getParentI(curI);
        while(curI > 0 && this.arr[curI] < this.arr[parentI]) {
            this.swap(curI, parentI);
            curI = parentI;
            parentI = this.getParentI(curI);
        }
    }

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

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

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

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

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

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

    has(val:number):boolean {
        if(this.hashTB[val]) return true;
        
        return false;
    }

    add(val:number):void {
        this.hashTB[val] = true;
    }
}class SmallestInfiniteSet {
    private heap = new MinHeap();
    private set = new HashSet();
    private curInt = 1;

    popSmallest():number {
        if(!this.heap.isEmpty()){
            const val = this.heap.pop();
            this.set.remove(val);
            return val;
        }

        return this.curInt++;
    }

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

        this.heap.add(num);
        this.set.add(num);
    }
}

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

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

    pop():number {
        const val = this.arr[0];
        const last =  this.arr.pop();

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

        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 smallestChildI = rightChildI >= this.arr.length || this.arr[rightChildI] > this.arr[leftChildI]? leftChildI: rightChildI;

                   this.swap(smallestChildI, curI);
                        curI = smallestChildI;
                        leftChildI = this.getLeftChildI(curI);
                        rightChildI = this.getRightChildI(curI);
                }

        return val;
    }

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

        let curI = this.arr.length - 1;
        let parentI = this.getParentI(curI);
        while(curI > 0 && this.arr[curI] < this.arr[parentI]) {
            this.swap(curI, parentI);
            curI = parentI;
            parentI = this.getParentI(curI);
        }
    }

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

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

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

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

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

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

    has(val:number):boolean {
        if(this.hashTB[val]) return true;
        
        return false;
    }

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

THE PROBLEM

This time, I notice the interesting thing about this while loop:

while((leftChildI < this.arr.length && this.arr[leftChildI] < this.arr[curI]) || (rightChildI < this.arr.length && this.arr[rightChildI] < this.arr[curI]))

You only recognize how interesting it is when you know about the short-circuit. Basically, it will check for the leftChild first, if there is no left child, it will stop immediately. If there is a left child, it will check if the leftChild is smaller than current child, if it is, it doesn't need to check anything more, because now, we know that there is at least 1 child that is smaller than the current child, so we need to swap. It the left child is greater than the current child, we are still not sure if the right child is also greater than the current child. So, we check the right child. If there is no right child, we stop immediately, because the only child is greater than the current child. But if there is a right child, we need to check if it is smaller than the current child. If it is, we need to do the thing inside the loop. If it is not, we stop.

The beautiful thing about this while loop is that it cleverly describes what we need to do in real life.

Revised by ChatGPT

This loop leverages the concept of short-circuit evaluation in its condition, optimizing the check for whether a swap between the current node and one of its children is necessary:

Left Child Check: The condition first examines if the left child exists (by checking if leftChildI is within bounds of the array) and if it is smaller than the current node (this.arr[leftChildI] < this.arr[curI]). If both conditions are true, the loop proceeds without checking the right child, as we've already found a smaller child, indicating a need for re-balancing.
Right Child Consideration: If the left child does not exist or is not smaller, the condition then evaluates the right child in a similar manner. This ensures that if the left child does not necessitate a swap, but a right child exists and is smaller, the loop will still proceed to consider swapping with the right child.
Efficiency and Precision: This approach is efficient because it avoids unnecessary comparisons. By exploiting short-circuiting, it minimizes the checks needed to decide if a swap should occur. If the left child us smaller, there's no need to check the right child to initiate a swap. Conversely, if the left child is not smaller or does not exist, the right child is then evaluated to ensure the heap property is restored.

The beauty of this while loop lies in its concise yet precise logic for maintaining the min heap's order. It mirrors a pragmatic approach in real-life decision-making, where actions are taken based in the first relevant condition met, ensuring efficiency and effectiveness in reorganizing the heap after removal.