@datastructures-js/heap

What is @datastructures-js/heap?

@datastructures-js/heap is an npm package that provides implementations of heap data structures, including MinHeap and MaxHeap. These data structures are useful for efficiently managing and retrieving the minimum or maximum element in a collection, which is particularly useful in algorithms like priority queues, Dijkstra's algorithm, and more.

What are @datastructures-js/heap's main functionalities?

MinHeap

The MinHeap feature allows you to create a heap where the smallest element is always at the root. This is useful for scenarios where you need to efficiently retrieve the minimum element.

const { MinHeap } = require('@datastructures-js/heap');
const minHeap = new MinHeap();
minHeap.insert(5);
minHeap.insert(3);
minHeap.insert(8);
console.log(minHeap.extractRoot()); // 3
console.log(minHeap.root()); // 5

MaxHeap

The MaxHeap feature allows you to create a heap where the largest element is always at the root. This is useful for scenarios where you need to efficiently retrieve the maximum element.

const { MaxHeap } = require('@datastructures-js/heap');
const maxHeap = new MaxHeap();
maxHeap.insert(5);
maxHeap.insert(3);
maxHeap.insert(8);
console.log(maxHeap.extractRoot()); // 8
console.log(maxHeap.root()); // 5

Heapify an Array

The heapify feature allows you to convert an existing array into a heap. This is useful for initializing a heap with a predefined set of elements.

const { MinHeap } = require('@datastructures-js/heap');
const array = [5, 3, 8, 1, 2];
const minHeap = MinHeap.heapify(array);
console.log(minHeap.root()); // 1

Heap Sort

Heap sort is a sorting algorithm that uses a heap to sort elements. This feature demonstrates how to use a MinHeap to sort an array in ascending order.

const { MinHeap } = require('@datastructures-js/heap');
const array = [5, 3, 8, 1, 2];
const minHeap = MinHeap.heapify(array);
const sortedArray = [];
while (!minHeap.isEmpty()) {
  sortedArray.push(minHeap.extractRoot());
}
console.log(sortedArray); // [1, 2, 3, 5, 8]

Other packages similar to @datastructures-js/heap

heap-js

heap-js is another npm package that provides heap data structures. It supports both MinHeap and MaxHeap and offers similar functionalities to @datastructures-js/heap. One key difference is that heap-js provides additional customization options for the comparator function, allowing for more flexible heap implementations.

js-priority-queue

js-priority-queue is a package that implements a priority queue using a binary heap. It offers similar functionalities to @datastructures-js/heap but focuses more on the priority queue aspect. It provides a simple API for managing elements with priorities, making it a good choice for applications that require priority-based element retrieval.

heap

heap is a minimalistic package that provides a binary heap implementation. It supports both MinHeap and MaxHeap and offers basic heap operations. Compared to @datastructures-js/heap, it has a smaller feature set but is lightweight and easy to use for simple heap operations.

README

@datastructures-js/heap

a complete javascript implementation for the Min/Max Heap data structures & Heap Sort algorithm.

Min Heap	Max Heap

Table of Contents

• Install
• API
  • require
  • import
  • Construction
  • .insert(key, value)
  • .root()
  • .leaf()
  • .extractRoot()
  • .size()
  • .clone()
  • .sort()
  • .clear()
  • HeapNode
• Build
• License

install

npm install --save @datastructures-js/heap

API

require

const { MinHeap, MaxHeap } = require('@datastructures-js/heap');

import

import { MinHeap, MaxHeap } from '@datastructures-js/heap';

Construction

using "new"

creates an empty heap.

Example

const minHeap = new MinHeap();

const maxHeap = new MaxHeap();

using ".heapify(list)"

converts an existing array to a heap.

params
name	type	item type
list	array	number, string or object literal with key/value props

return
MinHeap or MaxHeap

runtime
O(n)

Example

const numList = [
  50,
  80,
  { key: 30, value: 'something' },
  90,
  { key: 60, value: null },
  40,
  { key: 20, value: { name: 'test' } }
];

const strList = [
  'm',
  'x',
  { key: 'f', value: 'something' },
  'b',
  { key: 'z', value: null },
  'k',
  { key: 'c', value: { name: 'test' } }
];

const minHeap = MinHeap.heapify(numList);

const maxHeap = MaxHeap.heapify(strList);

.insert(key, value)

insert a node into the heap.

params
name	type
key	number or string
value	object

return
HeapNode

runtime
O(log(n))

Example

const minHeap = new MinHeap();

const maxHeap = new MaxHeap();

minHeap.insert(50);
minHeap.insert(80);
minHeap.insert(30, 'something');
minHeap.insert(90);
minHeap.insert(60, null);
minHeap.insert(40);
minHeap.insert(20, { name: 'test' });

maxHeap.insert('m');
maxHeap.insert('x');
maxHeap.insert('f', 'something');
maxHeap.insert('b');
maxHeap.insert('z', null);
maxHeap.insert('k');
maxHeap.insert('c', { name: 'test' });

.root()

returns the root without removing it.

return
HeapNode

runtime
O(1)

Example

const min = minHeap.root();
console.log(min.getKey()); // 20
console.log(min.getValue()); // { name: 'test' }

const max = maxHeap.root();
console.log(max.getKey()); // 'z'
console.log(max.getValue()); // null

.leaf()

returns the node with the max key in MinHeap, or with the min key in MaxHeap.

return
HeapNode

runtime
O(1)

Example

const maxLeaf = minHeap.leaf();
console.log(maxLeaf.getKey()); // 90

const minLeaf = maxHeap.leaf();
console.log(minLeaf.getKey()); // 'b'

.extractRoot()

removes and returns the root node in the heap.

return
HeapNode

runtime
O(log(n))

Example

const min = minHeap.extractRoot();
console.log(min.getKey()); // 20
console.log(min.getValue()); // { name: 'test' }
console.log(minHeap.root().getKey()); // 30

const max = maxHeap.extractRoot();
console.log(max.getKey()); // 'z'
console.log(max.getValue()); // null
console.log(maxHeap.root().getKey()); // 'x'

.size()

returns the number of nodes in the heap.

return
number

runtime
O(1)

Example

console.log(minHeap.size()); // 6
console.log(maxHeap.size()); // 6

.clone()

creates a shallow copy of a heap by slicing the nodes array and passing it to a new heap instance.

return
MinHeap or MaxHeap

runtime
O(n)

Example

const minHeapClone = minHeap.clone();
minHeapClone.extractRoot();

console.log(minHeapClone.root().getKey()); // 40
console.log(minHeap.root().getKey()); // 30

.sort()

implements Heap Sort and sorts a Max Heap in ascneding order or a Min Heap in descending order.

return	description
array	a sorted list by key of HeapNode

runtime
O(n*log(n))

note : calling .sort() directly on a heap will mutate its nodes location. If you want to avoid that, you can sort a shallow copy of the heap.

Example

console.log(maxHeap.clone().sort()); // does not mutate the heap structure
/*
[
  HeapNode { key: 'b', value: undefined },
  HeapNode { key: 'c', value: { name: 'test' } },
  HeapNode { key: 'f', value: 'something' },
  HeapNode { key: 'k', value: undefined },
  HeapNode { key: 'm', value: undefined },
  HeapNode { key: 'x', value: undefined }
]
*/
console.log(maxHeap.root()); // HeapNode { key: 'x', value: undefined }

console.log(minHeap.clone().sort()); // does not mutate the heap structure
/*
[
  HeapNode { key: 90, value: undefined },
  HeapNode { key: 80, value: undefined },
  HeapNode { key: 60, value: null },
  HeapNode { key: 50, value: undefined },
  HeapNode { key: 40, value: undefined },
  HeapNode { key: 30, value: 'something' }
]
*/
console.log(minHeap.root()); // HeapNode { key: 30, value: 'something' }

To sort a list of elements directtly using Heap Sort, it can be done like:

const unsortedList = [3, 7, 2, 10, 4, 9, 8, 5, 1, 6];

const ascSorted = MaxHeap.heapify(unsortedList).sort().map((node) => node.getKey());
// [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

const descSorted = MinHeap.heapify(unsortedList).sort().map((node) => node.getKey());
// [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]

.clear()

clears the nodes in the heap.

runtime
O(1)

Example

minHeap.clear();
maxHeap.clear();

console.log(minHeap.size()); // 0
console.log(minHeap.root()); // null

console.log(maxHeap.size()); // 0
console.log(maxHeap.root()); // null

HeapNode

.getKey()

returns the node's key.

return
string or number

.getValue()

returns the node's associated value.

return
object

Build

lint + tests

grunt build

License

The MIT License. Full License is here

Changelog

[2.0.0] - 2020-04-06

Changed

• remove none-standard method .serialize().

Fixed

• return inserted node in Min/Max Heap.
• README
• jsdoc