BinaryHeap
Binary Heap Data Structure using an array implementation
Example
Import via NPM
var BinaryHeap = require("binaryheap-array");
|| Single element
var ch = new BinaryHeap();
ch.insert('T');
ch.insert('S');
ch.insert('R').insert('P');
ch.remove();
ch.peak();
ch.remove();
|| Object
var list = new BinaryHeap({ comparable: function(elm) { return elm.age; } });
list.insert({ 'name': 'John', 'age': 25 });
list.insert({ 'name': 'Mike', 'age': 21 });
list.insert({ 'name': 'Aisha', 'age': 33 });
list.insert({ 'name': 'Sarah', 'age': 20 });
list.remove();
list.size();
list.remove();
|| Priority Queue
Create a maximum or minimum priority queue on the fly
var maximumPQ = new BinaryHeap({ order:'asc' });
var minimumPQ = new BinaryHeap({ order:'dec' });
API
Method | Returns Type | Description |
---|
size | number | The size of the heap |
insert | object | Adds an element to the heap |
remove | object | Removes the root element (could be the max or min based on the configuration setting) |
print | undefined | Prints the tree structure of the binary heap |
peak | object | Peak on the root element, or the element that will get remove first |
Setting
Object | Type | Description |
---|
order | string | The order of the BinaryHeap either 'ascending' or 'descending' |
comparable | function | Choose what you need to compare, default to the inserted value see object example |
data | array | Pass in the data as an array ahead of time and we will handle the insertion for you |
O(n)
Type | Worst | Average |
---|
insert | O(log n) | O(log n) |
remove | O(log n) | O(log n) |
peak | O(1) | O(1) |
Graph
This graph is a representation of the algorithm used in this module
*-( (2 * i) + 1 )-˅
*-( 2 * i )-˅ ˅
[ 'ø', 'T', 'S', 'R', 'P', 'N', 'O', 'A', ...]
Empty *------^ ^
(2 * i) ^
*------------^
(2 * i) + 1
Reach out
Feel free to reach out with feedback via github: issue
, feature
, bug
, or enhancement
inputs are greatly appreciated
↳ Links: NPM | GitHub
© MIT