binaryheap-array
Binary Heap Data Structure using an array like implementation, super fast and easy to use
Last updated 7 months ago by khaledmohamedp .
MIT · Repository · Bugs · Original npm · Tarball · package.json
$ cnpm install binaryheap-array 
SYNC missed versions from official npm registry.

BinaryHeap

Binary Heap Data Structure using an array implementation

Istanbul Coverage Commitizen friendly Version License Downloads

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

Current Tags

  • 2.1.0                                ...           latest (7 months ago)

5 Versions

  • 2.1.0                                ...           7 months ago
  • 1.0.3                                ...           4 years ago
  • 1.0.2                                ...           4 years ago
  • 1.0.1                                ...           4 years ago
  • 1.0.0                                ...           4 years ago
Maintainers (1)
Downloads
Today 0
This Week 0
This Month 0
Last Day 0
Last Week 0
Last Month 0
Dependencies (1)
Dev Dependencies (5)
Dependents (0)
None

Copyright 2014 - 2016 © taobao.org |