@tyriar/fibonacci-heap - npm Package Compare versions

Comparing version 1.0.8 to 1.0.9

index.js

@@ -99,4 +99,3 @@ 'use strict';
     this.minNode = mergeLists(nextInRootList, extractedMin.child, this.compare);
-    if (nextInRootList) {
-      this.minNode = nextInRootList;
+    if (this.minNode) {
       this.minNode = consolidate(this.minNode, this.compare);
@@ -152,3 +151,3 @@ }
  *
- * @param {BinaryHeap} otherHeap The other heap.
+ * @param {FibonacciHeap} other The other heap.
  */
@@ -221,2 +220,3 @@ FibonacciHeap.prototype.union = function (other) {
 function cut(node, parent, minNode, compare) {
+  node.parent = undefined;
   parent.degree--;
@@ -223,0 +223,0 @@ if (node.next === node) {

package.json

 {
   "name": "@tyriar/fibonacci-heap",
-  "version": "1.0.8",
+  "version": "1.0.9",
   "description": "An implementation of the Fibonacci heap data structure",
@@ -5,0 +5,0 @@ "scripts": {

README.md

 # js-fibonacci-heap
- 
+
 [![Build Status](https://api.travis-ci.org/gwtw/js-fibonacci-heap.svg?branch=master)](http://travis-ci.org/gwtw/js-fibonacci-heap)
 [![Coverage Status](https://coveralls.io/repos/github/gwtw/js-fibonacci-heap/badge.svg?branch=master)](https://coveralls.io/github/gwtw/js-fibonacci-heap?branch=master)
 
-A JavaScript implementation of the [Fibonacci heap](http://www.growingwiththeweb.com/2014/06/fibonacci-heap.html) data structure.
+A JavaScript implementation of the [Fibonacci heap](http://www.growingwiththeweb.com/data-structures/fibonacci-heap/overview/) data structure.
 
-![](http://www.growingwiththeweb.com/images/2014/06/15/fibonacci-heap.svg)
+![](http://www.growingwiththeweb.com/images/data-structures/fibonacci-heap/fibonacci-heap.svg)
 
@@ -10,0 +10,0 @@ ## Features

test/fibonacci-heap-decrease-key-test.js

@@ -75,1 +75,28 @@ import test from 'ava';
 });
+
+test('should delete the node\'s parent reference after a cut', function (t) {
+  var heap = new Heap();
+  var node1 = heap.insert(1, null);
+  var node2 = heap.insert(2, null);
+  var node3 = heap.insert(3, null);
+  t.is(heap.size(), 3);
+
+  // Trigger a consolidate
+  //
+  //               2
+  //  1--2--3  ->  |
+  //               3
+  //
+  t.is(heap.extractMinimum(), node1);
+
+  // Decrease 3's key such that it's less than its parent
+  //
+  //  2      1
+  //  |  ->  |
+  //  3      2
+  //
+  heap.decreaseKey(node3, 1);
+
+  // Ensure 1's parent is undefined (the link to 2 has been cut)
+  t.is(node3.parent, undefined);
+});

test/fibonacci-heap-extract-min-test.js

@@ -106,1 +106,54 @@ import test from 'ava';
 });
+
+test('should consolidate after extract min is called on a tree with a single tree in the root node list', function (t) {
+  var heap = new Heap();
+  var node0 = heap.insert(0, null);
+  var node1 = heap.insert(1, null);
+  var node2 = heap.insert(2, null);
+  var node3 = heap.insert(3, null);
+  heap.insert(4, null);
+  heap.insert(5, null);
+  heap.insert(6, null);
+  heap.insert(7, null);
+  heap.insert(8, null);
+
+  // Extract minimum to trigger a consolidate nodes into a single Fibonacci tree.
+  //
+  //                                 __1
+  //                                / /|
+  //                               2 c d
+  //  1--2--3--4--5--6--7--8  ->  /| |
+  //                             a b f
+  //                             |
+  //                             e
+  //
+  t.is(heap.extractMinimum(), node0);
+
+  // Delete the 2nd smallest node in the heap which is the child of the single node in the root
+  // list. After this operation is performed the minimum node (1) is no longer pointing the minimum
+  // child in the node list!
+  //
+  //      __1
+  //     / /|         __1
+  //    2 c d        / /|  Note that a in this illustration could also be b, the main thing
+  //   /| |    ->   a c d  to take note of here is that a (or b) may not be the minimum child
+  //  a b f        /| |    of 1 anymore, despite being the node it's linked to.
+  //  |           e b f
+  //  e
+  //
+  heap.delete(node2);
+
+  // Extracting the minimum node at this point must trigger a consolidate on the new list, otherwise
+  // the next minimum may not be the actual minimum.
+  //
+  //
+  //      __1
+  //     / /|       a---c---d
+  //    a c d  ->  /|   |      -> Consolidate now to ensure the heap's minimum is correct
+  //   /| |       e b   f
+  //  e b f
+  //
+  //
+  t.is(heap.extractMinimum(), node1);
+  t.is(heap.findMinimum(), node3);
+});

No alert changes

Improved metrics

Total package byte prevSize

30583

increased by8.8%

Lines of code

815

increased by9.69%

No dependency changes