@thi.ng/heaps - npm Package Compare versions

Comparing version 0.1.0 to 0.2.0

CHANGELOG.md

@@ -6,2 +6,19 @@ # Change Log
 
+<a name="0.2.0"></a>
+# [0.2.0](https://github.com/thi-ng/umbrella/compare/@thi.ng/heaps@[e-mail]/heaps@0.2.0) (2018-04-22)
+
+
+### Bug Fixes
+
+* **heaps:** add DHeap ICopy/IEmpty impls, fix return types ([5894572](https://github.com/thi-ng/umbrella/commit/5894572))
+
+
+### Features
+
+* **heaps:** add min/max(), update heapify() and percolate methods ([c4bbee0](https://github.com/thi-ng/umbrella/commit/c4bbee0))
+* **heaps:** iterator now returns min() seq ([fccb3af](https://github.com/thi-ng/umbrella/commit/fccb3af))
+
+
+
+
 <a name="0.1.0"></a>
@@ -8,0 +25,0 @@ # 0.1.0 (2018-04-22)

dheap.d.ts

 import { DHeapOpts } from "./api";
 import { Heap } from "./heap";
+import { ICopy, IEmpty } from "@thi.ng/api/api";
 /**
@@ -12,3 +13,3 @@ * Generic d-ary heap / priority queue with configurable arity (default
  */
-export declare class DHeap<T> extends Heap<T> {
+export declare class DHeap<T> extends Heap<T> implements ICopy<DHeap<T>>, IEmpty<DHeap<T>> {
     /**
@@ -22,10 +23,2 @@ * Returns index of parent node or -1 if `idx < 1`.
     /**
-     * If `d=2` return index of other sibling. For all other `d`
-     * there're no unique solutions so always returns -1.
-     *
-     * @param idx
-     * @param d
-     */
-    static siblingIndex(idx: number, d?: number): number;
-    /**
      * Returns index of 1st child or -1 if `idx < 0`.
@@ -39,8 +32,10 @@ *
     constructor(values?: Iterable<T>, opts?: Partial<DHeapOpts<T>>);
+    copy(): any;
+    empty(): DHeap<T>;
     parent(n: number): T;
     children(n: number): T[];
     leaves(): T[];
-    heapify(): void;
-    protected percolateUp(i: number): void;
-    protected percolateDown(i: number): void;
+    heapify(vals?: T[]): void;
+    protected percolateUp(i: number, vals?: T[]): void;
+    protected percolateDown(i: number, vals?: T[]): void;
 }

dheap.js

@@ -33,12 +33,2 @@ "use strict";
     /**
-     * If `d=2` return index of other sibling. For all other `d`
-     * there're no unique solutions so always returns -1.
-     *
-     * @param idx
-     * @param d
-     */
-    static siblingIndex(idx, d = 4) {
-        return d === 2 ? heap_1.Heap.siblingIndex(idx) : -1;
-    }
-    /**
      * Returns index of 1st child or -1 if `idx < 0`.
@@ -52,2 +42,8 @@ *
     }
+    copy() {
+        return super.copy();
+    }
+    empty() {
+        return new DHeap(null, { compare: this.compare, d: this.d });
+    }
     parent(n) {
@@ -71,9 +67,8 @@ n = DHeap.parentIndex(n, this.d);
     }
-    heapify() {
-        for (var i = ((this.values.length - 1) / this.d) | 0; i >= 0; i--) {
-            this.percolateDown(i);
+    heapify(vals = this.values) {
+        for (var i = ((vals.length - 1) / this.d) | 0; i >= 0; i--) {
+            this.percolateDown(i, vals);
         }
     }
-    percolateUp(i) {
-        const vals = this.values;
+    percolateUp(i, vals = this.values) {
         const node = vals[i];
@@ -93,4 +88,3 @@ const d = this.d;
     }
-    percolateDown(i) {
-        const vals = this.values;
+    percolateDown(i, vals = this.values) {
         const n = vals.length;
@@ -97,0 +91,0 @@ const d = this.d;

heap.d.ts

@@ -21,3 +21,2 @@ import { ICopy, ILength, IEmpty, Comparator } from "@thi.ng/api/api";
     static parentIndex(idx: number): number;
-    static siblingIndex(idx: number): number;
     static childIndex(idx: number): number;
@@ -35,12 +34,25 @@ protected values: T[];
     pop(): T;
-    pushPop(val: T): T;
+    pushPop(val: T, vals?: T[]): T;
     into(vals: Iterable<T>): this;
     replaceHead(val: T): T;
-    heapify(): void;
-    sorted(): IterableIterator<T>;
+    heapify(vals?: T[]): void;
+    /**
+     * Returns the largest `n` values (or less) in heap, based on
+     * comparator ordering.
+     *
+     * @param n
+     */
+    max(n?: number): T[];
+    /**
+     * Returns the smallest `n` values (or less) in heap, based on
+     * comparator ordering.
+     *
+     * @param n
+     */
+    min(n?: number): T[];
     parent(n: number): T;
     children(n: number): T[];
     leaves(): T[];
-    protected percolateUp(i: number): void;
-    protected percolateDown(i: number): void;
+    protected percolateUp(i: number, vals?: T[]): void;
+    protected percolateDown(i: number, vals?: T[]): void;
 }

heap.js

@@ -32,5 +32,2 @@ "use strict";
     }
-    static siblingIndex(idx) {
-        return idx > 0 ? idx + 1 - ((idx & 1) << 1) : -1;
-    }
     static childIndex(idx) {
@@ -40,3 +37,3 @@ return idx >= 0 ? (idx << 1) + 1 : -1;
     *[Symbol.iterator]() {
-        yield* this.values;
+        yield* this.min();
     }
@@ -79,4 +76,3 @@ get length() {
     }
-    pushPop(val) {
-        const vals = this.values;
+    pushPop(val, vals = this.values) {
         const head = vals[0];
@@ -86,3 +82,3 @@ if (vals.length > 0 && this.compare(head, val) < 0) {
             val = head;
-            this.percolateDown(0);
+            this.percolateDown(0, vals);
         }
@@ -103,14 +99,50 @@ return val;
     }
-    heapify() {
-        for (var i = (this.values.length - 1) >> 1; i >= 0; i--) {
-            this.percolateDown(i);
+    heapify(vals = this.values) {
+        for (var i = (vals.length - 1) >> 1; i >= 0; i--) {
+            this.percolateDown(i, vals);
         }
     }
-    *sorted() {
-        const h = this.copy();
-        let x;
-        while ((x = h.pop()) !== undefined) {
-            yield x;
+    /**
+     * Returns the largest `n` values (or less) in heap, based on
+     * comparator ordering.
+     *
+     * @param n
+     */
+    max(n = this.values.length) {
+        const vals = this.values;
+        const cmp = this.compare;
+        const res = vals.slice(0, n);
+        if (!n) {
+            return res;
         }
+        this.heapify(res);
+        for (let m = vals.length; n < m; n++) {
+            this.pushPop(vals[n], res);
+        }
+        return res.sort((a, b) => cmp(b, a));
     }
+    /**
+     * Returns the smallest `n` values (or less) in heap, based on
+     * comparator ordering.
+     *
+     * @param n
+     */
+    min(n = this.values.length) {
+        const vals = this.values;
+        const cmp = this.compare;
+        const res = vals.slice(0, n).sort(cmp);
+        if (!n) {
+            return res;
+        }
+        let x = res[n - 1], y;
+        for (let i = n, m = vals.length; i < m; i++) {
+            y = vals[i];
+            if (cmp(y, x) < 0) {
+                res.splice(binarySearch(res, y, 0, n, cmp), 0, y);
+                res.pop();
+                x = res[n - 1];
+            }
+        }
+        return res;
+    }
     parent(n) {
@@ -137,4 +169,3 @@ n = Heap.parentIndex(n);
     }
-    percolateUp(i) {
-        const vals = this.values;
+    percolateUp(i, vals = this.values) {
         const node = vals[i];
@@ -153,4 +184,3 @@ const cmp = this.compare;
     }
-    percolateDown(i) {
-        const vals = this.values;
+    percolateDown(i, vals = this.values) {
         const n = vals.length;
@@ -178,1 +208,14 @@ const node = vals[i];
 exports.Heap = Heap;
+function binarySearch(vals, x, lo, hi, cmp) {
+    let m;
+    while (lo < hi) {
+        m = (lo + hi) >>> 1;
+        if (cmp(x, vals[m]) < 0) {
+            hi = m;
+        }
+        else {
+            lo = m + 1;
+        }
+    }
+    return lo;
+}

package.json

 {
     "name": "@thi.ng/heaps",
-    "version": "0.1.0",
+    "version": "0.2.0",
     "description": "Generic binary heap & d-ary heap implementations with customizable ordering",
@@ -5,0 +5,0 @@ "main": "./index.js",

No alert changes

Improved metrics

Total package byte prevSize

26127

increased by7.07%

Lines of code

436

increased by11.22%

No dependency changes