@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