Heap

class Heap {
    constructor(comparator) {
        this.values = [];
        this.fn = comparator || Heap.minComparator;
    }

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

    pop() {
        return this.remove(this.values[0]);
    }

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

    add(value) {
        this.values.push(value);
        this.#bubbleUp(this.size() - 1);
    }

    remove(value) {
        const index = this.values.indexOf(value);
        // If value is not in heap, return
        if (index === -1) {
            return undefined;
        }
        if (index === this.size() - 1) {
            return this.values.pop();
        }
        this.#swap(index, this.size() - 1);
        const val = this.values.pop();
        this.#bubbleDown(this.#bubbleUp(index));
        return val;
    }

    #swap(index_1, index_2) {
        const temp = this.values[index_1];
        this.values[index_1] = this.values[index_2];
        this.values[index_2] = temp;
    }

    #compare(index_1, index_2) {
        return this.fn(this.values[index_1], this.values[index_2]);
    }

    #bubbleUp(index) {
        // If index is 0, we are at the root
        if (index === 0) {
            return index;
        }
        const parentIndex = Math.floor((index - 1) / 2);
        if (this.#compare(parentIndex, index)) {
            this.#swap(parentIndex, index);
            this.#bubbleUp(parentIndex);
        }
        return index;
    }

    #bubbleDown(index) {
        const leftChildIndex = 2 * index + 1;
        const rightChildIndex = 2 * index + 2;
        let largestIndex = index;
        if (leftChildIndex < this.size() && this.#compare(largestIndex, leftChildIndex)) {
            largestIndex = leftChildIndex;
        }
        if (rightChildIndex < this.size() && this.#compare(largestIndex, rightChildIndex)) {
            largestIndex = rightChildIndex;
        }
        if (largestIndex !== index) {
            this.#swap(index, largestIndex);
            this.#bubbleDown(largestIndex);
        }
        return index;
    }
}

Heap.minComparator = (a, b) => a > b;
Heap.maxComparator = (a, b) => a < b;

Operation	Time Complexity
size	O(1)
isEmpty	O(1)
pop	O(log n)
peek	O(1)
add	O(log n)
remove	O(log n)
#swap	O(1)
#compare	O(1) // depends on the implementation
#bubbleDown	O(log n)
#bubbleUp	O(log n)