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');

// 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'

|| Object

// 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 }

|| Priority Queue

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' });

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