feat(heaps): add PairingHeap

thi-ng · Dec 23, 2019 · 748da44 · 748da44
1 parent af747d0
commit 748da44
Show file tree

Hide file tree

Showing 2 changed files with 168 additions and 1 deletion.
diff --git a/packages/heaps/src/index.ts b/packages/heaps/src/index.ts
@@ -1,3 +1,4 @@
 export * from "./api";
-export * from "./dheap";
 export * from "./heap";
+export * from "./dheap";
+export * from "./pairing";
diff --git a/packages/heaps/src/pairing.ts b/packages/heaps/src/pairing.ts
@@ -0,0 +1,166 @@
+import {
+    Comparator,
+    Fn,
+    ICopy,
+    IEmpty,
+    ILength,
+    IStack
+} from "@thi.ng/api";
+import { compare } from "@thi.ng/compare";
+import { HeapOpts } from "./api";
+
+interface Node<T> {
+    v?: T;
+    c: Node<T>[];
+    p?: Node<T>;
+}
+
+export class PairingHeap<T>
+    implements
+        ICopy<PairingHeap<T>>,
+        IEmpty<PairingHeap<T>>,
+        ILength,
+        IStack<T, T, PairingHeap<T>> {
+    protected compare: Comparator<T>;
+    protected root!: Node<T>;
+    protected _size!: number;
+
+    constructor(vals?: Iterable<T>, opts?: HeapOpts<T>) {
+        opts = Object.assign({ compare: compare }, opts);
+        this.compare = opts.compare;
+        this.clear();
+        vals && this.into(vals);
+    }
+
+    get length() {
+        return this._size;
+    }
+
+    *[Symbol.iterator]() {
+        const acc: T[] = [];
+        this.visit((x) => (acc.push(x), true));
+        yield* acc;
+    }
+
+    clear() {
+        this.root = { v: undefined, p: undefined, c: [] };
+        this._size = 0;
+    }
+
+    empty() {
+        return new PairingHeap<T>(undefined, { compare });
+    }
+
+    copy() {
+        const heap = this.empty();
+        return heap;
+    }
+
+    push(v: T) {
+        this.root = this.merge(this.root, {
+            v,
+            p: undefined,
+            c: []
+        });
+        this._size++;
+        return this;
+    }
+
+    pop() {
+        const res = this.root.v;
+        if (res !== undefined) {
+            const children = this.root.c;
+            if (children.length) {
+                this.root = this.mergePairs(children);
+            } else {
+                this.root.v = undefined;
+            }
+            this._size--;
+        }
+        return res;
+    }
+
+    pushPop(x: T) {
+        if (!this._size || this.compare(x, this.root.v!) < 0) {
+            return x;
+        }
+        const res = this.pop();
+        this.push(x);
+        return res;
+    }
+
+    peek() {
+        return this._size ? this.root.v : undefined;
+    }
+
+    into(vals: Iterable<T>) {
+        for (let i of vals) {
+            this.push(i);
+        }
+        return this;
+    }
+
+    /**
+     * Computes union with given heap and clears `heap`, i.e. this heap
+     * will take ownership of `heap`'s items (if any).
+     *
+     * @param heap
+     */
+    meld(heap: PairingHeap<T>) {
+        if (!heap._size) return this;
+        if (!this._size) {
+            this.root = heap.root;
+            this._size = heap._size;
+        } else {
+            this._size += heap._size;
+            this.root =
+                this.compare(this.peek()!, heap.peek()!) <= 0
+                    ? this.merge(this.root, heap.root)
+                    : this.merge(heap.root, this.root);
+        }
+        heap.clear();
+        return this;
+    }
+
+    visit(fn: Fn<T, boolean>) {
+        this._size && this.doVisit(fn, this.root);
+    }
+
+    protected doVisit(fn: Fn<T, boolean>, root: Node<T>): boolean {
+        if (fn(root.v!)) {
+            const children = root.c;
+            let ok = true;
+            for (let i = children.length; ok && --i >= 0; ) {
+                ok = this.doVisit(fn, children[i]);
+            }
+            return ok;
+        }
+        return false;
+    }
+
+    protected merge(a: Node<T>, b: Node<T>) {
+        if (a.v === undefined) {
+            return b;
+        }
+        if (this.compare(a.v, b.v!) < 0) {
+            a.c.push(b);
+            b.p = a;
+            return a;
+        }
+        b.c.push(a);
+        a.p = b;
+        return b;
+    }
+
+    protected mergePairs(heaps: Node<T>[]) {
+        const n = heaps.length - 1;
+        let root = heaps[n];
+        if (n > 0) {
+            for (let i = n; --i >= 0; ) {
+                root = this.merge(root, heaps[i]);
+            }
+        }
+        root.p = undefined;
+        return root;
+    }
+}