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 javascript implementation for Heap data structure & Heap Sort algorithm.

Min Heap	Max Heap

Install
require
import
API
Build
License

install

npm install --save @datastructures-js/heap

require

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

import

import { MinHeap, MaxHeap, CustomHeap, HeapNode } from '@datastructures-js/heap';
// HeapNode is the key/value interface for MinHeap/MaxHeap

API

constructor

creates an empty heap. use CustomHeap when you need advanced comparison logic between heap nodes. For primitive comparisons, use MinHeap/MaxHeap.

JS

const minHeap = new MinHeap();

const maxHeap = new MaxHeap();

// comparator receievs the parent (a) and child (b) in each comparison
// and should return a number, if bigger than 0, it will swap nodes.
const customMinHeap = new CustomHeap((a, b) => a.count - b.count);

const customMaxHeap = new CustomHeap((a, b) => a.name < b.name ? 1 : -1);

TS

const minHeap = new MinHeap<number, [number, number]>();

const maxHeap = new MaxHeap<string, { name: string }>();

// comparator receievs the parent (a) and child (b) in each comparison
// and should return a number, if bigger than 0, it will swap nodes.
const customMinHeap = new CustomHeap<{ count: number }>(
  (a, b) => a.count - b.count
);

const customMaxHeap = new CustomHeap<{ name: string }>(
  (a, b) => a.name < b.name ? 1 : -1
);

.insert(key[, value])

insert a node into the heap. If value is provided (anything except undefined), the node is stored as {key: ..., value: ...} otherwise, the node is the key (number or string). For CustomHeap, anything can be inserted as a comparator is provided to compare nodes.

MinHeap/MaxHeap

params	return	runtime
key: T (number \| string) value: U (any)	MinHeap<T, U> \| MaxHeap<T, U>	O(log(n))

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

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

CustomHeap

params	return	runtime
key: T	CustomHeap<T>	O(log(n))

customMaxHeap
  .insert({ name: 'm' })
  .insert({ name: 'x' })
  .insert({ name: 'f' })
  .insert({ name: 'b' })
  .insert({ name: 'z' })
  .insert({ name: 'k' })
  .insert({ name: 'c' });

.extractRoot()

removes and returns the root node in the heap.

MinHeap/MaxHeap

return	runtime
number \| string \| HeapNode	O(log(n))

console.log(minHeap.extractRoot()); // { key: 20, value: { name: 'test' } }
console.log(minHeap.extractRoot()); // { key: 30, value: 'something' }
console.log(minHeap.extractRoot()); // 40

console.log(maxHeap.extractRoot()); // { key: 'z', value: null }
console.log(maxHeap.extractRoot()); // 'x'
console.log(maxHeap.extractRoot()); // 'm'

CustomHeap

return	runtime
T	O(log(n))

console.log(customMaxHeap.extractRoot()); // { name: 'z' }
console.log(customMaxHeap.extractRoot()); // { name: 'x' }
console.log(customMaxHeap.extractRoot()); // { name: 'm' }

.root()

returns the root node without removing it.

MinHeap/MaxHeap

return	runtime
number \| string \| HeapNode	O(1)

console.log(minHeap.root()); // 50

console.log(maxHeap.root()); // 'k'

CustomHeap

return	runtime
T	O(1)

console.log(customMaxHeap.root()); // { name: 'k' }

.leaf()

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

MinHeap/MaxHeap

return	runtime
number \| string \| HeapNode	O(1)

console.log(minHeap.leaf()); // 90

console.log(maxHeap.leaf()); // 'b'

CustomHeap

return	runtime
T	O(1)

console.log(customMaxHeap.leaf()); // { name: 'b' }

.size()

returns the number of nodes in the heap.

return	runtime
number	O(1)

console.log(minHeap.size()); // 4
console.log(maxHeap.size()); // 4
console.log(customMaxHeap.size()); // 4

.clone()

creates a shallow copy of the heap.

return	runtime
MinHeap \| MaxHeap \| CustomHeap	O(n)

const minHeapClone = minHeap.clone();
minHeapClone.extractRoot();
console.log(minHeapClone.root()); // 60
console.log(minHeap.root()); // 50

const maxHeapClone = maxHeap.clone();
maxHeapClone.extractRoot();
console.log(maxHeapClone.root()); // { key: 'f', value: 'something' }
console.log(maxHeap.root()); // 'k'

const customMaxHeapClone = customMaxHeap.clone();
customMaxHeap.extractRoot();
console.log(customMaxHeap.root()); // { name: 'f' }
console.log(customMaxHeapClone.root()); // { name: 'k' }

.isValid()

checks if the heap is valid.

return	runtime
boolean	O(log(n))

console.log(minHeap.isValid()); // true

console.log(maxHeap.isValid()); // true

console.log(customMaxHeap.isValid()); // true

.fix()

fixes a heap by making the necessary changes in node positions.

return	runtime
MinHeap \| MaxHeap \| CustomHeap	O(log(n))

console.log(minHeap.fix().isValid()); // true

console.log(maxHeap.fix().isValid()); // true

console.log(customMaxHeap.fix().isValid()); // true

.sort()

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

MinHeap/MaxHeap

return	runtime
array<number\|string\|HeapNode>	O(n*log(n))

note: calling .sort() directly on a heap will mutate its nodes location. To avoid that, you might either sort a shallow copy. You can also use use .fix() to fix the mutated heap positions

console.log(maxHeap.clone().sort()); // sorting a copy of the heap
/*
[
  'b',
  { key: 'c', value: { name: 'test' } },
  { key: 'f', value: 'something' },
  'k'
]
*/
console.log(maxHeap.root()); // 'k'

console.log(minHeap.sort()); // will mutate the heap
/*
[ 90, 80, { key: 60, value: null }, 50 ]
*/
console.log(minHeap.isValid()); // false
minHeap.fix(); // fix it
console.log(minHeap.isValid()); // true

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

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

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

CustomHeap

return	runtime
array<T>	O(n*log(n))

// sorting custom max heap in ascending order
console.log(customMaxHeap.clone().sort());
/*
[
  { name: 'b' },
  { name: 'c' },
  { name: 'f' },
  { name: 'k' },
  { name: 'm' },
  { name: 'x' },
  { name: 'z' }
]
*/

.clear()

clears the nodes in the heap.

runtime
O(1)

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

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

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

Heap.heapify(list)

Heapifies an existing list. It returns a heap instance as well as changing the list positions properly.

MinHeap/MaxHeap

params	return	runtime
list: array<number \| string \| HeapNode>	MinHeap \| MaxHeap	O(n)

JS

const numList = [50, 80, 30, 90, 60, 40, 20];
MinHeap.heapify(numList);
console.log(numList); // [20, 60, 30, 90, 80, 50, 40]

const strList = ['m', 'x', 'f', 'b',  'z', 'k', 'c'];
const maxHeap = MaxHeap.heapify(strList);
console.log(strList); // ['z', 'x', 'k', 'b', 'm', 'f', 'c']
console.log(maxHeap.isValid()); // true

const objList = [
  { key: 50, value: 't1' },
  { key: 80, value: 't2' },
  { key: 30, value: 't3' },
  { key: 90, value: 't4' },
  { key: 60, value: 't5' },
  { key: 40, value: 't6' },
  { key: 20, value: 't7' }
];
MinHeap.heapify(objList);
console.log(objList);
/*
[
  { key: 20, value: 't7' },
  { key: 60, value: 't5' },
  { key: 30, value: 't3' },
  { key: 90, value: 't4' },
  { key: 80, value: 't2' },
  { key: 50, value: 't1' },
  { key: 40, value: 't6' }
]
*/

TS

const numList = [50, 80, 30, 90, 60, 40, 20];
MinHeap.heapify<number>(numList);
console.log(numList); // [20, 60, 30, 90, 80, 50, 40]

const objList = [
  { key: 50, value: 't1' },
  { key: 80, value: 't2' },
  { key: 30, value: 't3' },
  { key: 90, value: 't4' },
  { key: 60, value: 't5' },
  { key: 40, value: 't6' },
  { key: 20, value: 't7' }
];
MinHeap.heapify<number, string>(objList);
console.log(objList);
/*
[
  { key: 20, value: 't7' },
  { key: 60, value: 't5' },
  { key: 30, value: 't3' },
  { key: 90, value: 't4' },
  { key: 80, value: 't2' },
  { key: 50, value: 't1' },
  { key: 40, value: 't6' }
]
*/

CustomHeap

params	return	runtime
list: array<T> comparator: (a: T, b: T) => number	CustomHeap<T>	O(n)

const counts = [
  { count: 50 },
  { count: 80 },
  { count: 30 },
  { count: 90 },
  { count: 60 },
  { count: 40 },
  { count: 20 }
];
CustomHeap.heapify<{ count: number }>(counts, (a, b) => a.count - b.count);

console.log(counts); // minHeap list
/*
[
  { count: 20 },
  { count: 60 },
  { count: 30 },
  { count: 90 },
  { count: 80 },
  { count: 50 },
  { count: 40 }
]
*/

Heap.isHeapified(list)

Checks if a given list is heapified.

MinHeap/MaxHeap

params	return	runtime
list: array<number \| string \| HeapNode>	boolean	O(log(n))

JS

MinHeap.isHeapified([50, 80, 30, 90, 60, 40, 20]); // false

MinHeap.isHeapified([20, 60, 30, 90, 80, 50, 40]); // true

MaxHeap.isHeapified(['m', 'x', 'f', 'b', 'z', 'k', 'c']); // false

MaxHeap.isHeapified(['z', 'x', 'k', 'b', 'm', 'f', 'c']); // true

TS

MinHeap.isHeapified<number>([20, 60, 30, 90, 80, 50, 40]); // true

MaxHeap.isHeapified<string>(['z', 'x', 'k', 'b', 'm', 'f', 'c']); // true

CustomHeap

params	return	runtime
list: array<T> comparator: (a: T, b: T) => number	boolean	O(log(n))

const counts = [
  { count: 20 },
  { count: 60 },
  { count: 30 },
  { count: 90 },
  { count: 80 },
  { count: 50 },
  { count: 40 }
];

console.log(CustomHeap.isHeapified<{ count: number }>(counts, (a, b) => a.count - b.count)); // true

Build

grunt build

License

The MIT License. Full License is here