anilpai · June 28, 2023 17:30 · Jun 28, 2023
diff --git a/binaryheap.ts b/binaryheap.ts
@@ -0,0 +1,72 @@
+/* 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);