PriorityQueue.js

class T {
    constructor(endTime, roomId) {
        this.endTime = endTime;
        this.roomId = roomId;
    }
}


class PriorityQueueTest {
    constructor(comparator = (a, b) => a - b) {
        this._heap = [];
        this._comparator = comparator;
    }

    enqueue(value) {
        this._heap.push(value);
        this._siftUp();
        return this.size();
    }

    dequeue() {
        const poppedValue = this.peek();
        const bottom = this.size() - 1;
        if (bottom > 0) {
            this._swap(0, bottom);
        }
        this._heap.pop();
        this._siftDown();
        return poppedValue;
    }

    peek() {
        return this._heap[0];
    }

    size() {
        return this._heap.length;
    }

    isEmpty() {
        return this.size() === 0;
    }

    _greater(i, j) {
        return this._comparator(this._heap[i], this._heap[j]) < 0;
    }

    _swap(i, j) {
        [this._heap[i], this._heap[j]] = [this._heap[j], this._heap[i]];
    }

    _siftUp() {
        let node = this.size() - 1;
        while (node > 0 && this._greater(node, Math.floor((node - 1) / 2))) {
            this._swap(node, Math.floor((node - 1) / 2));
            node = Math.floor((node - 1) / 2);
        }
    }

    _siftDown() {
        let node = 0;
        while (
            (node * 2 + 1 < this.size() && this._greater(node * 2 + 1, node)) ||
            (node * 2 + 2 < this.size() && this._greater(node * 2 + 2, node))
        ) {
            let maxChild =
                node * 2 + 2 < this.size() && this._greater(node * 2 + 2, node * 2 + 1)
                    ? node * 2 + 2
                    : node * 2 + 1;
            this._swap(node, maxChild);
            node = maxChild;
        }
    }
}