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.

Min Heap	Max Heap

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