# @tyriar/fibonacci-heap

> An implementation of the Fibonacci heap data structure

Latest version **2.0.9** (published 2018-12-02) · MIT license · 0 weekly downloads

## Install

```sh
npm install @tyriar/fibonacci-heap
pnpm add @tyriar/fibonacci-heap
yarn add @tyriar/fibonacci-heap
bun add @tyriar/fibonacci-heap
```

## Health

**Score 25/100 (F)** — status: abandoned.

Positive: has types; no vulnerabilities; high quality score.

Warnings: low downloads; no esm support.

Negative: abandoned; low maintenance score.

## Facts

| | |
|---|---|
| Version | 2.0.9 |
| Published | 2018-12-02 |
| First published | 2015-11-09 |
| Weekly downloads | 0 |
| License | MIT |
| TypeScript types | bundled |
| Module format | CommonJS |
| Dependencies | 0 |
| Unpacked size | 36.3 KB |
| Known vulnerabilities | 0 |
| Install scripts | no |
| GitHub stars | 17 |
| Author | Daniel Imms |
| Maintainers | tyriar |
| Keywords | A*, computer science, data structure, dijkstra, heap, priority queue, tree |

## Links

- npm: https://www.npmjs.com/package/@tyriar/fibonacci-heap
- Repository: https://github.com/gwtw/ts-fibonacci-heap
- Issues: https://github.com/gwtw/ts-fibonacci-heap/issues
- npm.io page: https://npm.io/package/@tyriar/fibonacci-heap

## Alternatives

- [cron](https://npm.io/package/cron.md) — 4.9M weekly downloads
- [@vercel/queue](https://npm.io/package/@vercel/queue.md) — 731.6K weekly downloads
- [create-sonicjs](https://npm.io/package/create-sonicjs.md) — 1.6K weekly downloads
- [@exellix/jobs-api](https://npm.io/package/@exellix/jobs-api.md) — 941 weekly downloads
- [@forwardimpact/libskill](https://npm.io/package/@forwardimpact/libskill.md) — 575 weekly downloads

## Recent versions

- 2.0.9 (latest) — 2018-12-02
- 2.0.9-beta1 (beta) — 2018-12-02
- 2.0.8 — 2018-09-04
- 2.0.7 — 2018-01-22
- 2.0.6 — 2018-01-22
- 2.0.5 — 2018-01-22
- 2.0.4 — 2018-01-01
- 2.0.3 — 2018-01-01
- 2.0.2 — 2018-01-01
- 2.0.1 — 2018-01-01
- 2.0.0 — 2018-01-01
- 1.0.10 — 2016-11-20
- 1.0.9 — 2016-11-05
- 1.0.8 — 2016-10-16
- 1.0.7 — 2016-05-28
- … 7 more at https://npm.io/package/@tyriar/fibonacci-heap/versions

## README

# ts-fibonacci-heap

[![Build Status](https://api.travis-ci.org/gwtw/ts-fibonacci-heap.svg?branch=master)](http://travis-ci.org/gwtw/ts-fibonacci-heap)
[![Coverage Status](https://coveralls.io/repos/github/gwtw/ts-fibonacci-heap/badge.svg?branch=master)](https://coveralls.io/github/gwtw/ts-fibonacci-heap?branch=master)

A TypeScript implementation of the [Fibonacci heap](http://www.growingwiththeweb.com/data-structures/fibonacci-heap/overview/) 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.

![](http://www.growingwiththeweb.com/images/data-structures/fibonacci-heap/fibonacci-heap.svg)

## 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

```bash
npm install --save @tyriar/fibonacci-heap
```

## Usage

See the [typings file](./typings/fibonacci-heap.d.ts) for the full API.

```typescript
// 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

---
_Source: https://npm.io/package/@tyriar/fibonacci-heap · Machine-readable twin of the npm.io package page. Health data is recomputed on every publish._