little-ds-toolkit - npm Package Compare versions

Comparing version 1.0.0 to 1.1.0

lib/heap.js

@@ -1,2 +0,1 @@
-
 function Heap (comp, onMove) {
@@ -13,3 +12,3 @@ this.comp = comp || function (a, b) {
   this.data = []
-  this.onMove = onMove || function () {}
+  this.onMove = onMove
 }
@@ -32,4 +31,6 @@
   var tmp = this.data[x]
-  this.onMove(this.data[x], y, x)
-  this.onMove(this.data[y], x, y)
+  if (this.onMove) {
+    this.onMove(this.data[x], y, x)
+    this.onMove(this.data[y], x, y)
+  }
   this.data[x] = this.data[y]
@@ -54,32 +55,43 @@ this.data[y] = tmp
 
-Heap.prototype._bubbleDown = function bubbleDown (i) {
+Heap.prototype._heapify = function heapify (i) {
   var data = this.data
   var comp = this.comp
-  var child1Index, child2Index,
-    child1isSmaller, child2isSmaller
-  while (i < data.length) {
-    child1Index = Heap.getChild1Index(i)
-    child2Index = Heap.getChild2Index(i)
-    child1isSmaller = typeof data[child1Index] !== 'undefined' ? comp(data[child1Index], data[i]) < 0 : false
-    child2isSmaller = typeof data[child2Index] !== 'undefined' ? comp(data[child2Index], data[i]) < 0 : false
-    if (child1isSmaller && child2isSmaller) {
-      if (comp(data[child1Index], data[child2Index]) < 0) {
-        this._swap(child1Index, i)
-        i = child1Index
-      } else {
-        this._swap(child2Index, i)
-        i = child2Index
-      }
-    } else if (child1isSmaller) {
+
+  var child1Index = Heap.getChild1Index(i)
+  var child2Index = Heap.getChild2Index(i)
+  var child1isSmaller = data[child1Index] !== undefined ? comp(data[child1Index], data[i]) < 0 : false
+  var child2isSmaller = data[child2Index] !== undefined ? comp(data[child2Index], data[i]) < 0 : false
+  if (child1isSmaller && child2isSmaller) {
+    if (comp(data[child1Index], data[child2Index]) < 0) {
       this._swap(child1Index, i)
-      i = child1Index
-    } else if (child2isSmaller) {
+      return child1Index
+    } else {
       this._swap(child2Index, i)
-      i = child2Index
-    } else {
-      return i
+      return child2Index
     }
+  } else if (child1isSmaller) {
+    this._swap(child1Index, i)
+    return child1Index
+  } else if (child2isSmaller) {
+    this._swap(child2Index, i)
+    return child2Index
+  } else {
+    return null
   }
 }
 
+Heap.prototype._bubbleDown = function bubbleDown (i) {
+  var len = this.data.length
+  while (i !== null && i < len) {
+    i = this._heapify(i)
+  }
+}
+
+Heap.prototype.buildHeap = function (items) {
+  this.data = items
+  for (var i = this.data.length / 2; i >= 0; i--) {
+    this._heapify(i)
+  }
+}
+
 Heap.prototype.pushAll = function (items) {
@@ -93,3 +105,5 @@ for (var i = 0; i < items.length; i++) {
   this.data.push(item)
-  this.onMove(this.data[this.data.length - 1], this.data.length - 1)
+  if (this.onMove) {
+    this.onMove(this.data[this.data.length - 1], this.data.length - 1)
+  }
   this._bubbleUp(this.data.length - 1)
@@ -105,4 +119,6 @@ }
   var root = this.data[0]
-  if (typeof root === 'undefined') return
-  this.onMove(this.data[0], undefined, 0)
+  if (root === undefined) return
+  if (this.onMove) {
+    this.onMove(this.data[0], undefined, 0)
+  }
 
@@ -113,3 +129,5 @@ var last = this.data.pop()
     this.data[0] = last
-    this.onMove(this.data[0], 0)
+    if (this.onMove) {
+      this.onMove(this.data[0], 0)
+    }
     this._bubbleDown(0)
@@ -161,5 +179,5 @@ }
   if (i === -1) return
-
-  this.onMove(this.data[i], undefined, i)
-
+  if (this.onMove) {
+    this.onMove(this.data[i], undefined, i)
+  }
   if (i === this.data.length - 1) {
@@ -184,4 +202,5 @@ last = this.data.pop()
   if (i === -1) return
-  this.onMove(this.data[i], undefined, i)
-
+  if (this.onMove) {
+    this.onMove(this.data[i], undefined, i)
+  }
   this.data.push(value)
@@ -188,0 +207,0 @@

lib/min-max-heap.js

@@ -39,3 +39,3 @@ var Heap = require('./heap')
 
-MinMaxHeap.prototype.push = function (item) {
+MinMaxHeap.prototype.push = function push (item) {
   var wrapped = wrapValue(item)
@@ -46,4 +46,10 @@ this.minHeap.push(wrapped)
 
-MinMaxHeap.prototype.pushAll = function (items) {
+MinMaxHeap.prototype.buildHeap = function buildHeap (items) {
   var wrapped = items.map(wrapValue)
+  this.minHeap.buildHeap(wrapped)
+  this.maxHeap.buildHeap(wrapped)
+}
+
+MinMaxHeap.prototype.pushAll = function pushAll (items) {
+  var wrapped = items.map(wrapValue)
   this.minHeap.pushAll(wrapped)
@@ -53,11 +59,11 @@ this.maxHeap.pushAll(wrapped)
 
-MinMaxHeap.prototype.peekMin = function () {
+MinMaxHeap.prototype.peekMin = function peekMin () {
   return this.minHeap.peek().value
 }
 
-MinMaxHeap.prototype.peekMax = function () {
+MinMaxHeap.prototype.peekMax = function peekMax () {
   return this.maxHeap.peek().value
 }
 
-MinMaxHeap.prototype.popMin = function () {
+MinMaxHeap.prototype.popMin = function popMin () {
   var item = this.minHeap.pop()
@@ -71,3 +77,3 @@ if (!item) {
 
-MinMaxHeap.prototype.popMax = function () {
+MinMaxHeap.prototype.popMax = function popMax () {
   var item = this.maxHeap.pop()
@@ -81,3 +87,3 @@ if (!item) {
 
-MinMaxHeap.prototype.popMaxAll = function () {
+MinMaxHeap.prototype.popMaxAll = function popMaxAll () {
   var out = []
@@ -90,3 +96,3 @@ while (this.size()) {
 
-MinMaxHeap.prototype.popMinAll = function () {
+MinMaxHeap.prototype.popMinAll = function popMinAll () {
   var out = []
@@ -99,7 +105,7 @@ while (this.size()) {
 
-MinMaxHeap.prototype.size = function () {
+MinMaxHeap.prototype.size = function size () {
   return this.minHeap.size()
 }
 
-MinMaxHeap.prototype.remove = function (value) {
+MinMaxHeap.prototype.remove = function remove (value) {
   var isEqual = value
@@ -106,0 +112,0 @@

package.json

 {
   "name": "little-ds-toolkit",
-  "version": "1.0.0",
+  "version": "1.1.0",
   "description": "A small collection of useful data structures",
@@ -5,0 +5,0 @@ "main": "index.js",

README.md

@@ -69,10 +69,12 @@ little-ds-toolkit
 ```
-There "pushAll" and "popAll" methods are shortcuts to insert an array of items in the heap, or retrieving them. Combined together the can be used to build the heapsort sorting algorithm:
+With buildHeap you can populate the heap with the values in an array (it resets the heap). It is very efficient, only O(n). The array used as argument will be mutated!
+"popAll" is a utility method to return all items in the heap. These two methods, combined together the can be used to build the heapsort sorting algorithm:
 ```js
 var heap = new Heap();
-heap.pushAll(unsorted_array);
-heap.popAll(); // returns a sorted array
+heap.buildHeap(unsorted_array); // O(n)
+heap.popAll(); // returns a sorted array O(nlogn)
 ```
 The "toArray" method returns the inner array representation (partially sorted).
 
+
 Advanced features: updating item order and removing items
@@ -124,2 +126,3 @@ ---------------------------------------------------------
 * toArray: return a partially sorted array O(1)
+* buildHeap: build the heap starting with an array O(n)
 
@@ -126,0 +129,0 @@ union-find

tests/heap.spec.js

@@ -224,2 +224,11 @@ /* eslint-env node, mocha */
 
+  describe('buildHeap', function () {
+    it('must push an array', function () {
+      var h = new Heap()
+      h.buildHeap([4, 3, 2, 1])
+      assert.deepEqual(h.data, [1, 4, 2, 3])
+      assert.deepEqual(h.popAll(), [1, 2, 3, 4])
+    })
+  })
+
   describe('onMove', function () {
@@ -226,0 +235,0 @@ it('must keep the positions updated', function () {

New alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Fixed alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Major refactor

Supply chain risk

Package has recently undergone a major refactor. It may be unstable or indicate significant internal changes. Use caution when updating to versions that include significant changes.

Found 1 instance in 1 package

Improved metrics

Total package byte prevSize

38617

increased by2.66%

Lines of code

972

increased by3.51%

Number of lines in readme file

211

increased by1.44%

Number of medium supply chain risk alerts

0

decreased by-100%

No dependency changes