Package Exports

@datastructures-js/heap

This package does not declare an exports field, so the exports above have been automatically detected and optimized by JSPM instead. If any package subpath is missing, it is recommended to post an issue to the original package (@datastructures-js/heap) to support the "exports" field. If that is not possible, create a JSPM override to customize the exports field for this package.

Readme

@datastructures-js/heap

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

heap

Install
API
- require
- import
- Creating a Heap
  - new
  - .heapify(list)
- .insert(key, value)
- .root()
- .extractRoot()
- .serialize()
- .size()
- .clone()
- .sort()
- .clear()
Build

install

npm install --save @datastructures-js/heap

API

require

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

import

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

create a heap

new

creates an empty heap.

Example

const minHeap = new MinHeap();

const maxHeap = new MaxHeap();

.heapify(list)

converts an array of objects to a heap.

runtime	params	return
O(n)	list: {array} elements can be {number}, {string} or serialized heap node.	{MinHeap} or {MaxHeap}

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.

runtime	params
O(log(n))	key: {number} or {string} the value that is used to compare nodes in the heap value: {object} the value that is associated with a key

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()

peeks on the root without removing it.

runtime	params	return
O(1)	list: {array} elements can be {number}, {string} or serialized heap node.	{HeapNode} .getKey() returns the node's key that is used to compare with other nodes. .getValue() returns the value that is associated with the key. .serialize() returns an object literal of key/value of the node.

runtime

params

return

O(1)

list: {array}
elements can be {number}, {string} or serialized heap node.

{HeapNode}

.getKey() returns the node's key that is used to compare with other nodes.

.getValue() returns the value that is associated with the key.

.serialize() returns an object literal of key/value of the node.

Example

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

const max = maxHeap.root();
console.log(max.getKey()); // 'z'
console.log(max.getValue()); // null
console.log(max.serialize()); // { key: 'z', value: null }

.extractRoot()

removes and returns the root node in the heap.

runtime	return
O(log(n))	{HeapNode}

Example

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

const max = maxHeap.extractRoot();
console.log(max.getKey()); // 'z'
console.log(max.getValue()); // null
console.log(max.serialize()); // { key: 'z', value: null }
console.log(maxHeap.root().getKey()); // 'x'

.serialize()

converts the heap into a list of serialized nodes objects.

runtime	return
O(n)	{array}

Example

console.log(minHeap.serialize());
/*
[
  { key: 30, value: 'something' },
  { key: 60, value: null },
  { key: 40, value: undefined },
  { key: 90, value: undefined },
  { key: 80, value: undefined },
  { key: 50, value: undefined }
]
*/

console.log(maxHeap.serialize());
/*
[
  { key: 'x', value: undefined },
  { key: 'm', value: undefined },
  { key: 'k', value: undefined },
  { key: 'b', value: undefined },
  { key: 'c', value: { name: 'test' } },
  { key: 'f', value: 'something' }
]
*/

.size()

runtime	return
O(1)	{number}

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.

runtime	return
O(n)	{MinHeap} or {MaxHeap}

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.

runtime	return
O(n*log(n))	{array} a sorted list by key of the heap nodes.

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(n => n.getKey());
// [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

const descSorted = MinHeap.heapify(unsortedList).sort().map(n => n.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

Build

lint + tests

grunt build

License

The MIT License. Full License is here