Socket
Socket
Sign inDemoInstall

@tyriar/fibonacci-heap

Package Overview
Dependencies
0
Maintainers
1
Versions
22
Alerts
File Explorer

Advanced tools

Install Socket

Detect and block malicious and high-risk dependencies

Install

@tyriar/fibonacci-heap

An implementation of the Fibonacci heap data structure


Version published
Maintainers
1
Weekly downloads
578,309
decreased by-28.36%

Weekly downloads

Readme

Source

ts-fibonacci-heap

Build Status Coverage Status

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

OperationComplexity
clearΘ(1)*
decreaseKeyΘ(1)*
deleteO(log n)*
extractMinimumO(log n)*
findMinimumΘ(1)
insertΘ(1)
isEmptyΘ(1)
sizeΘ(n)
unionΘ(1)

* amortized

Keywords

FAQs

Last updated on 02 Dec 2018

Did you know?

Socket for GitHub automatically highlights issues in each pull request and monitors the health of all your open source dependencies. Discover the contents of your packages and block harmful activity before you install or update your dependencies.

Install

Related posts

SocketSocket SOC 2 Logo

Product

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

Stay in touch

Get open source security insights delivered straight into your inbox.


  • Terms
  • Privacy
  • Security

Made with ⚡️ by Socket Inc