Binary Heap Data Structure using an array implementation
var BinaryHeap = require("binaryheap-array");var ch = new BinaryHeap();
ch.insert('T');
ch.insert('S');
// You can also chain inserts :)
ch.insert('R').insert('P');
// Removes the largest element first
ch.remove(); // 'T'
// You can also peak before you remove
ch.peak(); // 'S'
ch.remove(); // 'S'// Use the 'comparable' property to choose what you need to compare ahead of time
// In our example we want to compare the age
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(); // { name: 'Aisha', age: 33 }
list.size(); // 3
list.remove(); // { name: 'John', age: 25 }Create a maximum or minimum priority queue on the fly
// Choose the order of the binaryheap ascending, or descending
var maximumPQ = new BinaryHeap({ order:'asc' });
var minimumPQ = new BinaryHeap({ order:'dec' });| 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) |
undefined |
Prints the tree structure of the binary heap | |
| peak | object |
Peak on the root element, or the element that will get remove first |
| 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 |
| Type | Worst | Average |
|---|---|---|
| insert | O(log n) | O(log n) |
| remove | O(log n) | O(log n) |
| peak | O(1) | O(1) |
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
Feel free to reach out with feedback via github: issue, feature, bug, or enhancement inputs are greatly appreciated
© MIT
React
Typescript
Django
Laravel
Facebook
Microsoft
Google
Alibaba
D3
Tencent