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

KhaledMohamedP/BinaryHeap