@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

ts-fibonacci-heap

A TypeScript implementation of the Fibonacci heap data structure.

Note that the primary purpose of this library is education but it should work in a production environment as well. It's certainly not as performant as it could be as it optimises for readability, abstraction and safety over raw performance.

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

See the typings file for the full API.

// Import npm module
import { FibonacciHeap } from '@tyriar/fibonacci-heap';

// Construct FibonacciHeap
const heap = new FibonacciHeap<number, any>();
// 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()) {
  const 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
const heap2 = new FibonacciHeap<string, string>(function (a, b) {
  return (a.key + a.value).localeCompare(b.key + b.value);
});
heap2.insert('2', 'B');
heap2.insert('1', 'a');
heap2.insert('1', 'A');
heap2.insert('2', 'b');

// Extract all nodes in order
while (!heap2.isEmpty()) {
  const node = heap2.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