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 } = require('@datastructures-js/heap');

import

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

API

constructor

creates an empty heap.

JS

const minHeap = new MinHeap();

const maxHeap = new MaxHeap();

TS

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

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

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

params	return	runtime
key: number \| string value: any	MinHeap \| MaxHeap	O(log(n))

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

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

.extractRoot()

removes and returns the root node in the heap.

return	runtime
number \| string \| { key, value }	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'

.root()

returns the root node without removing it.

return	runtime
number \| string \| { key, value }	O(1)

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

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

.leaf()

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

return	runtime
number \| string \| { key, value }	O(1)

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

console.log(maxHeap.leaf()); // '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

.clone()

creates a shallow copy of the heap.

return	runtime
MinHeap \| MaxHeap	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'

.isValid()

checks if the heap is valid.

return	runtime
boolean	O(log(n))

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

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

.fix()

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

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

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

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

.sort()

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

return	runtime
array<number\|string\|object>	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]

.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(maxHeap.size()); // 0
console.log(maxHeap.root()); // null

Heap.heapify(list)

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

params	return	runtime
list: array<number \| string \| { key, value }>	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' }
]
*/

Heap.isHeapified(list)

Checks if a given list is heapified.

params	return	runtime
list: array<number \| string \| { key, value }>	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

Build

grunt build

License

The MIT License. Full License is here