123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124

// Min-Heap Implementation
class MinHeap {
    constructor() {
        this.heap = [];
    }

    // Helper function to swap two indices in the heap array
    swap(i, j) {
        const temp = this.heap[i];
        this.heap[i] = this.heap[j];
        this.heap[j] = temp;
    }

    // Push a new value into the heap
    push(val) {
        this.heap.push(val);
        this.heapifyUp(this.heap.length - 1);
    }

    // Pop the smallest value from the heap
    pop() {
        if (this.heap.length === 0) return null;
        if (this.heap.length === 1) return this.heap.pop();

        // Swap the first and last, then remove the last
        this.swap(0, this.heap.length - 1);
        const poppedValue = this.heap.pop();
        this.heapifyDown(0);
        return poppedValue;
    }

    // Return the smallest value (root) without popping
    top() {
        return this.heap.length > 0 ? this.heap[0] : null;
    }

    // Heapify up to maintain min-heap property
    heapifyUp(index) {
        let parentIndex = Math.floor((index - 1) / 2);
        while (
            index > 0 &&
            this.heap[index] < this.heap[parentIndex]
        ) {
            this.swap(index, parentIndex);
            index = parentIndex;
            parentIndex = Math.floor((index - 1) / 2);
        }
    }

    // Heapify down to maintain min-heap property
    heapifyDown(index) {
        const length = this.heap.length;
        let smallest = index;

        while (true) {
            let leftChild = 2 * index + 1;
            let rightChild = 2 * index + 2;

            if (
                leftChild < length &&
                this.heap[leftChild] < this.heap[smallest]
            ) {
                smallest = leftChild;
            }
            if (
                rightChild < length &&
                this.heap[rightChild] < this.heap[smallest]
            ) {
                smallest = rightChild;
            }
            if (smallest !== index) {
                this.swap(