New Case Study:See how Anthropic automated 95% of dependency reviews with Socket.Learn More →
Socket
Sign inDemoInstall
Socket
Sign inDemoInstall

@tyriar/fibonacci-heap

Package Overview
Dependencies
Maintainers
1
Versions
22
Alerts
File Explorer

Advanced tools

License
Socket logo

Install Socket

Detect and block malicious and high-risk dependencies

Install

@tyriar/fibonacci-heap - npm Package Compare versions

Comparing version 1.0.5 to 1.0.6

test/fibonacci-heap-decrease-key-test.js
test/fibonacci-heap-delete-test.js
test/fibonacci-heap-extract-min-test.js

18

package.json
{
"name": "@tyriar/fibonacci-heap",
"version": "1.0.5",
"version": "1.0.6",
"description": "An implementation of the Fibonacci heap data structure",
"scripts": {
"doc": "documentation-readme -s \"API\"",
"test": "xo --space 2 && nyc ava",
"test": "xo && nyc ava",
"coveralls": "nyc report --reporter=text-lcov | coveralls"

@@ -12,3 +12,3 @@ },

"type": "git",
"url": "https://github.com/Tyriar/js-fibonacci-heap.git"
"url": "https://github.com/GrowingWithTheWeb/js-fibonacci-heap.git"
},

@@ -28,12 +28,16 @@ "keywords": [

"bugs": {
"url": "https://github.com/Tyriar/js-fibonacci-heap/issues"
"url": "https://github.com/GrowingWithTheWeb/js-fibonacci-heap/issues"
},
"homepage": "https://github.com/Tyriar/js-fibonacci-heap",
"homepage": "https://github.com/GrowingWithTheWeb/js-fibonacci-heap",
"devDependencies": {
"ava": "*",
"@tyriar/heap-tests": "^1.0.2",
"ava": "^0.14.0",
"coveralls": "^2.11.4",
"documentation-readme": "^2.1.0",
"nyc": "^3.2.2",
"xo": "*"
"xo": "^0.15.0"
},
"xo": {
"space": 2
}
}

5

README.md
# js-fibonacci-heap [![NPM version](https://img.shields.io/npm/v/@tyriar/fibonacci-heap.svg?style=flat)](https://www.npmjs.org/package/@tyriar/fibonacci-heap)
[![Build Status](http://img.shields.io/travis/Tyriar/js-fibonacci-heap.svg?style=flat)](http://travis-ci.org/Tyriar/js-fibonacci-heap) [![Coverage Status](https://img.shields.io/coveralls/Tyriar/js-fibonacci-heap.svg?branch=master&service=github)](https://coveralls.io/github/Tyriar/js-fibonacci-heap?branch=master)
[![Build Status](http://img.shields.io/travis/GrowingWithTheWeb/js-fibonacci-heap.svg?style=flat)](http://travis-ci.org/GrowingWithTheWeb/js-fibonacci-heap)
[![Coverage Status](https://img.shields.io/coveralls/GrowingWithTheWeb/js-fibonacci-heap.svg?branch=master&service=github)](https://coveralls.io/github/GrowingWithTheWeb/js-fibonacci-heap?branch=master)

@@ -155,2 +156,2 @@ A JavaScript implementation of the [Fibonacci heap](http://www.growingwiththeweb.com/2014/06/fibonacci-heap.html) data structure.

- `otherHeap` **BinaryHeap** The other heap.
- `other`
- `other`

23

test/clear-test.js
import test from 'ava';
import FibonacciHeap from '../';
import Heap from '../';
import testHelper from '@tyriar/heap-tests/clear-tests';
test('should set the heap\'s size to 0', t => {
var heap = new FibonacciHeap();
heap.insert(1, null);
heap.insert(2, null);
heap.insert(3, null);
heap.clear();
t.is(heap.size(), 0);
t.end();
});
test('should set the heap\'s minimum node to undefined', t => {
var heap = new FibonacciHeap();
heap.insert(1, null);
heap.insert(2, null);
heap.insert(3, null);
heap.clear();
t.is(heap.findMinimum(), undefined);
t.end();
});
testHelper.run(test, Heap);

41

test/custom-compare-test.js
import test from 'ava';
import FibonacciHeap from '../';
import Heap from '../';
import testHelper from '@tyriar/heap-tests/custom-compare-tests';
test('should give a min heap given a non-reverse customCompare', t => {
var heap = new FibonacciHeap(function (a, b) {
return a.key - b.key;
});
var node3 = heap.insert(13, null);
var node4 = heap.insert(26, null);
var node2 = heap.insert(3, null);
var node1 = heap.insert(-6, null);
var node5 = heap.insert(27, null);
t.is(heap.size(), 5);
t.same(heap.extractMinimum().key, node1.key);
t.same(heap.extractMinimum().key, node2.key);
t.same(heap.extractMinimum().key, node3.key);
t.same(heap.extractMinimum().key, node4.key);
t.same(heap.extractMinimum().key, node5.key);
t.true(heap.isEmpty());
t.end();
});
test('should give a max heap given a reverse customCompare', t => {
var heap = new FibonacciHeap(function (a, b) {
return b.key - a.key;
});
var node3 = heap.insert(13, null);
var node4 = heap.insert(26, null);
var node2 = heap.insert(3, null);
var node1 = heap.insert(-6, null);
var node5 = heap.insert(27, null);
t.is(heap.size(), 5);
t.same(heap.extractMinimum().key, node5.key);
t.same(heap.extractMinimum().key, node4.key);
t.same(heap.extractMinimum().key, node3.key);
t.same(heap.extractMinimum().key, node2.key);
t.same(heap.extractMinimum().key, node1.key);
t.true(heap.isEmpty());
t.end();
});
testHelper.run(test, Heap);

132

test/decrease-key-test.js
import test from 'ava';
import FibonacciHeap from '../';
import Heap from '../';
import testHelper from '@tyriar/heap-tests/decrease-key-tests';
test('should throw an exception given a non-existent node', t => {
var heap = new FibonacciHeap();
t.throws(() => {
heap.decreaseKey(undefined, 2);
});
t.end();
});
test('should throw an exception given a new key larger than the old key', t => {
var heap = new FibonacciHeap();
t.throws(() => {
var node = heap.insert(1, null);
heap.decreaseKey(node, 2);
});
t.end();
});
test('should decrease the minimum node', t => {
var heap = new FibonacciHeap();
var node1 = heap.insert(1, null);
heap.insert(2, null);
heap.decreaseKey(node1, -3);
var key = heap.findMinimum().key;
t.same(key, node1.key);
t.is(key, -3);
t.end();
});
test('should decrease and bubble up a non-minimum node', t => {
var heap = new FibonacciHeap();
heap.insert(1, null);
var node2 = heap.insert(2, null);
heap.decreaseKey(node2, -3);
var key = heap.findMinimum().key;
t.same(key, node2.key);
t.is(key, -3);
t.end();
});
test('should decrease and bubble up a non-minimum node in a large heap', t => {
var heap = new FibonacciHeap();
heap.insert(13, null);
heap.insert(26, null);
heap.insert(3, null);
heap.insert(-6, null);
var node5 = heap.insert(27, null);
heap.insert(88, null);
heap.insert(59, null);
heap.insert(-10, null);
heap.insert(16, null);
heap.decreaseKey(node5, -11);
t.same(heap.findMinimum().key, node5.key);
t.end();
});
test('should leave a valid tree on a flat Fibonacci heap', t => {
var heap = new FibonacciHeap();
heap.insert(13, null);
heap.insert(26, null);
heap.insert(3, null);
heap.insert(-6, null);
heap.insert(27, null);
var node6 = heap.insert(88, null);
heap.insert(59, null);
heap.insert(-10, null);
heap.insert(16, null);
heap.decreaseKey(node6, -8);
t.same(heap.extractMinimum().key, -10);
t.same(heap.extractMinimum().key, -8);
t.same(heap.extractMinimum().key, -6);
t.same(heap.extractMinimum().key, 3);
t.same(heap.extractMinimum().key, 13);
t.same(heap.extractMinimum().key, 16);
t.same(heap.extractMinimum().key, 26);
t.same(heap.extractMinimum().key, 27);
t.same(heap.extractMinimum().key, 59);
t.end();
});
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();
});
testHelper.run(test, Heap);

207

test/delete-test.js
import test from 'ava';
import FibonacciHeap from '../';
import Heap from '../';
import testHelper from '@tyriar/heap-tests/delete-tests';
test('should delete the head of the heap', t => {
var heap = new FibonacciHeap();
var node1 = heap.insert(1, null);
var node2 = heap.insert(2, null);
heap.delete(node1);
t.is(heap.extractMinimum(), node2);
t.true(heap.isEmpty());
t.end();
});
test('should delete nodes in a flat Fibonacci heap', t => {
var heap = new FibonacciHeap();
var node3 = heap.insert(13, null);
var node4 = heap.insert(26, null);
var node2 = heap.insert(3, null);
var node1 = heap.insert(-6, null);
var node5 = heap.insert(27, null);
t.is(heap.size(), 5);
heap.delete(node3);
t.is(heap.size(), 4);
t.is(heap.extractMinimum(), node1);
t.is(heap.extractMinimum(), node2);
t.is(heap.extractMinimum(), node4);
t.is(heap.extractMinimum(), node5);
t.true(heap.isEmpty());
t.end();
});
test('should cut the node from the tree if the node is not the minimum it does not have a grandparent', t => {
var heap = new FibonacciHeap();
var node1 = heap.insert(1, null);
var node2 = heap.insert(2, null);
var node3 = heap.insert(3, null);
var node4 = heap.insert(4, null);
// Extract the minimum, forcing the construction of an order 2 tree which
// is changed to an order 0 and order 1 tree after the minimum is extracted.
//
// 1
// /| 3--2
// 1--2--3--4 -> 3 2 -> |
// | 4
// 4
//
t.is(heap.extractMinimum(), node1);
// Deleting the node should trigger a cut and cascadingCut on the heap.
heap.delete(node4);
t.is(heap.size(), 2);
t.is(heap.extractMinimum(), node2);
t.is(heap.extractMinimum(), node3);
t.true(heap.isEmpty());
t.end();
});
test('should cut the node from the tree if the node is not the minimum and it has a grandparent', 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);
// extractMinimum on 0 should trigger a cut and cascadingCut on the heap.
//
// __1
// / /|
// 5 3 2
// 0--1--2--3--4--5--6--7--8 -> /| |
// 7 6 4
// |
// 8
//
t.is(heap.extractMinimum(), node0);
// Delete node 8
//
// __1
// / /| __1
// 5 3 2 / /|
// /| | -> 5 3 2
// 7 6 4 /| |
// | 7 6 4
// 8
//
heap.delete(node8);
t.is(heap.size(), 7);
t.is(heap.extractMinimum(), node1);
t.is(heap.extractMinimum(), node2);
t.is(heap.extractMinimum(), node3);
t.is(heap.extractMinimum(), node4);
t.is(heap.extractMinimum(), node5);
t.is(heap.extractMinimum(), node6);
t.is(heap.extractMinimum(), node7);
t.true(heap.isEmpty());
t.end();
});
test('should cut the node from the tree if the node is not the minimum, it has a grandparent and its parent is marked', 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);
// Delete node 6, marking 5
//
// __1 __1
// / /| / /|
// 5 3 2 >5 3 2
// /| | -> / |
// 7 6 4 7 4
// | |
// 8 8
//
heap.delete(node6);
t.true(node5.isMarked);
// Delete node 7, cutting the sub-tree
//
// __1
// / /| 1--5
// >5 3 2 /| |
// / | -> 3 2 8
// 7 4 |
// | 4
// 8
//
heap.delete(node7);
t.true(node5.next === node1);
t.true(node2.next === node3);
t.true(node3.next === node2);
t.is(heap.size(), 6);
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() === node8);
t.true(heap.isEmpty());
t.end();
});
test('should correctly assign an indirect child when a direct child is cut from the parent', t => {
var heap = new FibonacciHeap();
var node0 = heap.insert(0, null);
heap.insert(1, null);
heap.insert(2, null);
heap.insert(3, null);
heap.insert(4, null);
var node5 = heap.insert(5, null);
var node6 = heap.insert(6, null);
var node7 = heap.insert(7, null);
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);
// Delete node 6, marking 5
//
// __1 __1
// / /| / /|
// 5 3 2 >5 3 2
// /| | -> / |
// 7 6 4 7 4
// | |
// 8 8
//
heap.delete(node6);
t.true(node5.child === node7);
t.end();
});
testHelper.run(test, Heap);

160

test/extract-min-test.js
import test from 'ava';
import FibonacciHeap from '../';
import Heap from '../';
import testHelper from '@tyriar/heap-tests/extract-min-tests';
test('extract-min should return undefined on an empty heap', t => {
var heap = new FibonacciHeap();
t.is(heap.extractMinimum(), undefined);
t.end();
});
test('should extract the minimum item from a heap', t => {
var heap = new FibonacciHeap();
var node5 = heap.insert(5, null);
var node3 = heap.insert(3, null);
var node4 = heap.insert(4, null);
var node1 = heap.insert(1, null);
var node2 = heap.insert(2, null);
t.same(heap.extractMinimum().key, node1.key);
t.same(heap.extractMinimum().key, node2.key);
t.same(heap.extractMinimum().key, node3.key);
t.same(heap.extractMinimum().key, node4.key);
t.same(heap.extractMinimum().key, node5.key);
t.end();
});
test('should extract the minimum item from a jumbled heap', t => {
var heap = new FibonacciHeap();
var node1 = heap.insert(1, null);
var node4 = heap.insert(4, null);
var node3 = heap.insert(3, null);
var node5 = heap.insert(5, null);
var node2 = heap.insert(2, null);
t.same(heap.extractMinimum().key, node1.key);
t.same(heap.extractMinimum().key, node2.key);
t.same(heap.extractMinimum().key, node3.key);
t.same(heap.extractMinimum().key, node4.key);
t.same(heap.extractMinimum().key, node5.key);
t.end();
});
test('should extract the minimum item from a heap containing negative items', t => {
var heap = new FibonacciHeap();
var node1 = heap.insert(-9, null);
var node4 = heap.insert(6, null);
var node3 = heap.insert(3, null);
var node5 = heap.insert(10, null);
var node2 = heap.insert(-4, null);
t.same(heap.extractMinimum().key, node1.key);
t.same(heap.extractMinimum().key, node2.key);
t.same(heap.extractMinimum().key, node3.key);
t.same(heap.extractMinimum().key, node4.key);
t.same(heap.extractMinimum().key, node5.key);
t.end();
});
test('should consolidate 8 nodes into a well formed order 1 tree', t => {
var heap = new FibonacciHeap();
var node0 = heap.insert(0, null);
var node1 = heap.insert(1, null);
var node2 = heap.insert(2, null);
// Extracting minimum should trigger consolidate.
//
// 1
// 0--1--2 -> |
// 2
//
t.is(heap.extractMinimum(), node0);
t.is(heap.size(), 2);
t.true(node1.parent === undefined);
t.true(node2.parent === node1);
t.true(node1.next === node1);
t.true(node2.next === node2);
t.true(node1.child === node2);
t.true(node2.child === undefined);
t.end();
});
test('should consolidate 8 nodes into a well formed order 2 tree', 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);
// Extracting minimum should trigger consolidate.
//
// 1
// /|
// 0--1--2--3--4 -> 3 2
// |
// 4
//
t.is(heap.extractMinimum(), node0);
t.is(heap.size(), 4);
t.true(node1.parent === undefined);
t.true(node2.parent === node1);
t.true(node3.parent === node1);
t.true(node4.parent === node3);
t.true(node1.next === node1);
t.true(node2.next === node3);
t.true(node3.next === node2);
t.true(node4.next === node4);
t.true(node1.child === node2);
t.true(node2.child === undefined);
t.true(node3.child === node4);
t.true(node4.child === undefined);
t.end();
});
test('should consolidate 8 nodes into a well formed order 3 tree', 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
// 1--2--3--4--5--6--7--8 -> /| |
// 7 6 4
// |
// 8
//
t.is(heap.extractMinimum(), node0);
t.true(node1.parent === undefined);
t.true(node2.parent === node1);
t.true(node3.parent === node1);
t.true(node4.parent === node3);
t.true(node5.parent === node1);
t.true(node6.parent === node5);
t.true(node7.parent === node5);
t.true(node8.parent === node7);
t.true(node1.next === node1);
t.true(node2.next === node5);
t.true(node3.next === node2);
t.true(node4.next === node4);
t.true(node5.next === node3);
t.true(node6.next === node7);
t.true(node7.next === node6);
t.true(node8.next === node8);
t.true(node1.child === node2);
t.true(node2.child === undefined);
t.true(node3.child === node4);
t.true(node4.child === undefined);
t.true(node5.child === node6);
t.true(node6.child === undefined);
t.true(node7.child === node8);
t.true(node8.child === undefined);
t.end();
});
testHelper.run(test, Heap);

14

test/find-minimum-test.js
import test from 'ava';
import FibonacciHeap from '../';
import Heap from '../';
import testHelper from '@tyriar/heap-tests/find-minimum-tests';
test('should return the minimum item from the heap', t => {
var heap = new FibonacciHeap();
heap.insert(5, null);
heap.insert(3, null);
heap.insert(1, null);
heap.insert(4, null);
heap.insert(2, null);
t.is(heap.findMinimum().key, 1);
t.end();
});
testHelper.run(test, Heap);

22

test/insert-test.js
import test from 'ava';
import FibonacciHeap from '../';
import Heap from '../';
import testHelper from '@tyriar/heap-tests/insert-tests';
test('should insert items into the heap', t => {
var heap = new FibonacciHeap();
heap.insert(1, null);
heap.insert(2, null);
heap.insert(3, null);
heap.insert(4, null);
heap.insert(5, null);
t.same(heap.size(), 5);
t.end();
});
test('should return the inserted node', t => {
var heap = new FibonacciHeap();
var ret = heap.insert(1, {foo: 'bar'});
t.is(ret.key, 1);
t.same(ret.value, {foo: 'bar'});
t.end();
});
testHelper.run(test, Heap);

13

test/is-empty-test.js
import test from 'ava';
import FibonacciHeap from '../';
import Heap from '../';
import testHelper from '@tyriar/heap-tests/is-empty-tests';
test('should return whether the heap is empty', t => {
var heap = new FibonacciHeap();
t.true(heap.isEmpty());
heap.insert(1, null);
t.false(heap.isEmpty());
heap.extractMinimum();
t.true(heap.isEmpty());
t.end();
});
testHelper.run(test, Heap);

29

test/size-test.js
import test from 'ava';
import FibonacciHeap from '../';
import Heap from '../';
import testHelper from '@tyriar/heap-tests/size-tests';
test('should return the size of the heap', t => {
var heap = new FibonacciHeap();
t.is(heap.size(), 0);
heap.insert(1, null);
t.is(heap.size(), 1);
heap.insert(2, null);
t.is(heap.size(), 2);
heap.insert(3, null);
t.is(heap.size(), 3);
heap.insert(4, null);
t.is(heap.size(), 4);
heap.insert(5, null);
t.is(heap.size(), 5);
heap.insert(6, null);
t.is(heap.size(), 6);
heap.insert(7, null);
t.is(heap.size(), 7);
heap.insert(8, null);
t.is(heap.size(), 8);
heap.insert(9, null);
t.is(heap.size(), 9);
heap.insert(10, null);
t.is(heap.size(), 10);
t.end();
});
testHelper.run(test, Heap);

95

test/union-test.js
import test from 'ava';
import FibonacciHeap from '../';
import Heap from '../';
import testHelper from '@tyriar/heap-tests/union-tests';
test('should union the 2 heaps together given 2 heaps of size 5 with overlapping elements added in order together', t => {
var heap = new FibonacciHeap();
heap.insert(0, null);
heap.insert(2, null);
heap.insert(4, null);
heap.insert(6, null);
heap.insert(8, null);
var other = new FibonacciHeap();
other.insert(1, null);
other.insert(3, null);
other.insert(5, null);
other.insert(7, null);
other.insert(9, null);
t.is(heap.size(), 5);
t.is(other.size(), 5);
heap.union(other);
t.is(heap.size(), 10);
for (var i = 0; i < 10; i++) {
t.is(heap.extractMinimum().key, i);
}
t.true(heap.isEmpty());
t.end();
});
test('should union the 2 heaps together given 2 heaps of size 5 with overlapping elements added in reverse order together', t => {
var heap = new FibonacciHeap();
heap.insert(9, null);
heap.insert(7, null);
heap.insert(5, null);
heap.insert(3, null);
heap.insert(1, null);
var other = new FibonacciHeap();
other.insert(8, null);
other.insert(6, null);
other.insert(4, null);
other.insert(2, null);
other.insert(0, null);
t.is(heap.size(), 5);
t.is(other.size(), 5);
heap.union(other);
t.is(heap.size(), 10);
for (var i = 0; i < 10; i++) {
t.is(heap.extractMinimum().key, i);
}
t.true(heap.isEmpty());
t.end();
});
test('should union the 2 heaps together', t => {
var heaps = constructJumbledHeaps(t);
heaps[0].union(heaps[1]);
t.is(heaps[0].size(), 10);
for (var i = 0; i < 10; i++) {
t.is(heaps[0].extractMinimum().key, i);
}
t.true(heaps[0].isEmpty());
t.end();
});
test('should union the 2 heaps together after extracting the minimum from each', t => {
var heaps = constructJumbledHeaps(t);
t.is(heaps[0].extractMinimum().key, 1);
t.is(heaps[1].extractMinimum().key, 0);
heaps[0].union(heaps[1]);
t.is(heaps[0].size(), 8);
for (var i = 2; i < 10; i++) {
t.is(heaps[0].extractMinimum().key, i);
}
t.true(heaps[0].isEmpty());
t.end();
});
function constructJumbledHeaps(t) {
var first = new FibonacciHeap();
first.insert(9, null);
first.insert(2, null);
first.insert(6, null);
first.insert(1, null);
first.insert(3, null);
t.is(first.size(), 5);
var second = new FibonacciHeap();
second.insert(4, null);
second.insert(8, null);
second.insert(5, null);
second.insert(7, null);
second.insert(0, null);
t.is(second.size(), 5);
return [first, second];
}
testHelper.run(test, Heap);
test/fibonacci-heap-test.js
.editorconfig

Sorry, the diff of this file is not supported yet

.travis.yml

Sorry, the diff of this file is not supported yet

SocketSocket SOC 2 Logo

Product

  • Package Alerts
  • Integrations
  • Docs
  • Pricing
  • FAQ
  • Roadmap
  • Changelog

About

Packages

npm

Go

Maven

PyPI

Rubygems

Stay in touch

Get open source security insights delivered straight into your inbox.

  • Terms
  • Privacy
  • Security

Made with ⚡️ by Socket Inc