binaryheap.ts

/* Priority Queue based Heap implementation in TypeScript */

class BinaryHeap<T> {
    private heapArray: T[] = [];

    constructor(private lessThan: (a:T, b:T) => boolean) {
    }

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

    push(v: T) {
        this.heapArray.push(v);
        let i = this.heapArray.length - 1;
        while(i > 0 && this.lessThan(this.heapArray[i], this.heapArray[this.parent(i)])) {
            swap(this.heapArray, i, this.parent(i));
            i = this.parent(i);
        }
    }

    pop() {
        if (this.heapArray.length === 0) throw new Error('Overflow');

        const [head] = this.heapArray;
        this.heapArray[0] = this.heapArray[this.heapArray.length - 1];
        this.heapArray.length -= 1;

        this.heapify(0);

        return head;
    }

    private heapify(i: number) {
        const l = this.left(i);
        const r = this.right(i);
        let smallest = i;
        if (l < this.heapArray.length && this.lessThan(this.heapArray[l], this.heapArray[i])) {
            smallest = l;
        }
        if (r < this.heapArray.length && this.lessThan(this.heapArray[r], this.heapArray[smallest])) {
            smallest = r;
        }
        if (smallest !== i) {
            swap(this.heapArray, smallest, i);
            this.heapify(smallest);
        }
    }

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

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

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


function swap<T>(list: T[], i: number, j: number): T[] {
    if (i !== j) {
        [list[i], list[j]] = [list[j], list[i]];
    }
    return list;
}


let heap = new BinaryHeap<number>((a, b) => a < b);