Giter Site home page Giter Site logo

js-binary-heap's Introduction

js-binary-heap

Build Status Coverage Status

A JavaScript implementation of the binary heap data structure.

Features

  • 100% test coverage
  • Supports all common heap operations*
  • Store keys with optional associated values
  • Optional custom compare function that can utilize both key and value to give full control over the order of the data

* except delete and decrease key

Install

npm install --save @tyriar/binary-heap

Usage

// Import npm module
var BinaryHeap = require('@tyriar/binary-heap';

// Construct BinaryHeap
var heap = new BinaryHeap();
// Insert keys only
heap.insert(3);
heap.insert(7);
// Insert keys and values
heap.insert(8, {foo: 'bar'});
heap.insert(1, {foo: 'baz'});

// Extract all nodes in order
while (!heap.isEmpty()) {
  var node = heap.extractMinimum();
  console.log('key: ' + node.key + ', value: ' + node.value);
}
// > key: 1, value: [object Object]
// > key: 3, value: undefined
// > key: 7, value: undefined
// > key: 8, value: [object Object]

// Construct custom compare BinaryHeap
heap = new BinaryHeap(function (a, b) {
  return (a.key + a.value).localeCompare(b.key + b.value);
});
heap.insert('2', 'B');
heap.insert('1', 'a');
heap.insert('1', 'A');
heap.insert('2', 'b');

// Extract all nodes in order
while (!heap.isEmpty()) {
  var node = heap.extractMinimum();
  console.log('key: ' + node.key + ', value: ' + node.value);
}
// > key: 1, value: a
// > key: 1, value: A
// > key: 2, value: b
// > key: 2, value: B

Operation time complexity

Operation Complexity
buildHeap Θ(n)
clear Θ(1)
extractMinimum Θ(log n)
findMinimum Θ(1)
insert Θ(log n)
isEmpty Θ(1)
size Θ(1)
union Θ(n)

API

BinaryHeap

Creates a binary heap.

Parameters

  • customCompare function An optional custom node comparison function.

buildHeap

Builds a heap with the provided keys and values, this will discard the heap's current data.

Parameters

  • keys Array An array of keys.
  • values Array An array of values. This must be the same size as the key array.

clear

Clears the heap's data, making it an empty heap.

extractMinimum

Extracts and returns the minimum node from the heap.

Returns Node node The heap's minimum node or undefined if the heap is empty.

findMinimum

Returns the minimum node from the heap.

Returns Node node The heap's minimum node or undefined if the heap is empty.

insert

Inserts a new key-value pair into the heap.

Parameters

  • key Object The key to insert.
  • value Object The value to insert.

Returns Node node The inserted node.

isEmpty

Returns boolean Whether the heap is empty.

size

Returns number The size of the heap.

union

Joins another heap to this one.

Parameters

  • otherHeap BinaryHeap The other heap.

Node

Creates a node.

Parameters

  • key Object The key of the new node.
  • value Object The value of the new node.

js-binary-heap's People

Contributors

tyriar avatar

Watchers

 avatar  avatar

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.