@tyriar/fibonacci-heap - npm Package Compare versions

Comparing version 1.0.2 to 1.0.3

index.js

@@ -185,6 +185,2 @@ 'use strict';
 var NodeListIterator = function (start) {
-  if (!start) {
-    return;
-  }
-
   this.items = [];
@@ -191,0 +187,0 @@ var current = start;

package.json

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

test/decrease-key-test.js

@@ -59,3 +59,3 @@ import test from 'ava';
 
-test('should leave a valid tree', t => {
+test('should leave a valid tree on a flat Fibonacci heap', t => {
   var heap = new FibonacciHeap();
@@ -83,1 +83,51 @@ heap.insert(13, null);
 });
+
+test('should leave a valid tree on a consolidated Fibonacci heap', t => {
+  var heap = new FibonacciHeap();
+  var node0 = heap.insert(0, null);
+  var node1 = heap.insert(1, null);
+  var node2 = heap.insert(2, null);
+  var node3 = heap.insert(3, null);
+  var node4 = heap.insert(4, null);
+  var node5 = heap.insert(5, null);
+  var node6 = heap.insert(6, null);
+  var node7 = heap.insert(7, null);
+  var node8 = heap.insert(8, null);
+
+  // Extracting minimum should trigger consolidate.
+  //
+  //                                    __1
+  //                                   / /|
+  //                                  5 3 2
+  //  0--1--2--3--4--5--6--7--8  ->  /| |
+  //                                7 6 4
+  //                                |
+  //                                8
+  //
+  t.is(heap.extractMinimum(), node0);
+
+  // Decrease node 8 to 0
+  //
+  //      __1
+  //     / /|        __1--0
+  //    5 3 2       / /|
+  //   /| |    ->  5 3 2
+  //  7 6 4       /| |
+  //  |          7 6 4
+  //  8
+  //
+  heap.decreaseKey(node8, 0);
+  t.true(node1.next === node8);
+
+  t.is(heap.size(), 8);
+  t.true(heap.extractMinimum() === node8);
+  t.true(heap.extractMinimum() === node1);
+  t.true(heap.extractMinimum() === node2);
+  t.true(heap.extractMinimum() === node3);
+  t.true(heap.extractMinimum() === node4);
+  t.true(heap.extractMinimum() === node5);
+  t.true(heap.extractMinimum() === node6);
+  t.true(heap.extractMinimum() === node7);
+  t.true(heap.isEmpty());
+  t.end();
+});

No alert changes

Improved metrics

Total package byte prevSize

38840

increased by3.94%

Lines of code

1154

increased by3.87%

No dependency changes