@tyriar/fibonacci-heap

What is @tyriar/fibonacci-heap?

@tyriar/fibonacci-heap is an npm package that provides an implementation of the Fibonacci heap data structure. This data structure is particularly useful for priority queue operations and is often used in algorithms that require efficient decrease-key operations, such as Dijkstra's and Prim's algorithms.

What are @tyriar/fibonacci-heap's main functionalities?

Insert

This feature allows you to insert elements into the Fibonacci heap. Each element has a key and a value. The key is used to maintain the heap property.

const { FibonacciHeap } = require('@tyriar/fibonacci-heap');
const heap = new FibonacciHeap();
heap.insert(1, 'A');
heap.insert(2, 'B');
console.log(heap.size()); // Output: 2

Extract Minimum

This feature allows you to extract the minimum element from the Fibonacci heap. The minimum element is the one with the smallest key.

const { FibonacciHeap } = require('@tyriar/fibonacci-heap');
const heap = new FibonacciHeap();
heap.insert(1, 'A');
heap.insert(2, 'B');
const min = heap.extractMinimum();
console.log(min.value); // Output: 'A'

Decrease Key

This feature allows you to decrease the key of a given node in the Fibonacci heap. This is particularly useful in algorithms like Dijkstra's shortest path algorithm.

const { FibonacciHeap } = require('@tyriar/fibonacci-heap');
const heap = new FibonacciHeap();
const node = heap.insert(3, 'C');
heap.decreaseKey(node, 1);
const min = heap.extractMinimum();
console.log(min.value); // Output: 'C'

Other packages similar to @tyriar/fibonacci-heap

heap

The 'heap' package provides a general-purpose binary heap implementation. While it is simpler and may be faster for small datasets, it does not support the efficient decrease-key operation that Fibonacci heaps are known for.

js-priority-queue

The 'js-priority-queue' package offers a priority queue implementation using a binary heap. It is easy to use and efficient for many applications but lacks the advanced features of Fibonacci heaps, such as efficient decrease-key operations.

priorityqueuejs

The 'priorityqueuejs' package provides a priority queue implementation using a binary heap. It is similar to 'js-priority-queue' but offers a different API. Like other binary heap implementations, it does not support efficient decrease-key operations.

README

js-fibonacci-heap

A JavaScript implementation of the Fibonacci heap data structure.

Features

• 100% test coverage
• Supports all common heap operations
• Store keys with optional associated values
• Optional custom compare function that can utilize both key and value to give full control over the order of the data

Install

npm install --save @tyriar/fibonacci-heap

Usage

// Import npm module
var FibonacciHeap = require('@tyriar/fibonacci-heap';

// Construct FibonacciHeap
var heap = new FibonacciHeap();
// Insert keys only
heap.insert(3);
heap.insert(7);
// Insert keys and values
heap.insert(8, {foo: 'bar'});
heap.insert(1, {foo: 'baz'});

// Extract all nodes in order
while (!heap.isEmpty()) {
  var node = heap.extractMinimum();
  console.log('key: ' + node.key + ', value: ' + node.value);
}
// > key: 1, value: [object Object]
// > key: 3, value: undefined
// > key: 7, value: undefined
// > key: 8, value: [object Object]

// Construct custom compare FibonacciHeap
heap = new FibonacciHeap(function (a, b) {
  return (a.key + a.value).localeCompare(b.key + b.value);
});
heap.insert('2', 'B');
heap.insert('1', 'a');
heap.insert('1', 'A');
heap.insert('2', 'b');

// Extract all nodes in order
while (!heap.isEmpty()) {
  var node = heap.extractMinimum();
  console.log('key: ' + node.key + ', value: ' + node.value);
}
// > key: 1, value: a
// > key: 1, value: A
// > key: 2, value: b
// > key: 2, value: B

Operation time complexity

Operation	Complexity
clear	Θ(1)*
decreaseKey	Θ(1)*
delete	O(log n)*
extractMinimum	O(log n)*
findMinimum	Θ(1)
insert	Θ(1)
isEmpty	Θ(1)
size	Θ(n)
union	Θ(1)

* amortized

API

FibonacciHeap

Creates a Fibonacci heap.

Parameters

• customCompare function An optional custom node comparison function.

clear

Clears the heap's data, making it an empty heap.

decreaseKey

Decreases a key of a node.

Parameters

• node Node The node to decrease the key of.
• newKey Object The new key to assign to the node.

delete

Deletes a node.

Parameters

• node Node The node to delete.

extractMinimum

Extracts and returns the minimum node from the heap.

Returns Node node The heap's minimum node or undefined if the heap is empty.

findMinimum

Returns the minimum node from the heap.

Returns Node node The heap's minimum node or undefined if the heap is empty.

insert

Inserts a new key-value pair into the heap.

Parameters

• key Object The key to insert.
• value Object The value to insert.

Returns Node node The inserted node.

isEmpty

Returns boolean Whether the heap is empty.

size

Returns number The size of the heap.

union

Joins another heap to this heap.

Parameters

• otherHeap BinaryHeap The other heap.
• other