binary-heap

Stability: 1 - Experimental

Binary heap.

Installation

npm install binary-heap

Tests

npm test

Usage

var Heap = require('binary-heap');

var heap1 = new Heap();
var heap2 = Heap.build({heap: [3,7,2,1]});

Overview

Documentation

Heap

A JavaScript implementation of a binary heap.

WARNING: This heap implementation uses 1-indexed arrays (instead of 0-indexed) arrays. Therefore, the indexes used in Heap.left(index), Heap.right(index) and others, are assuming that the binary tree representing the heap has a root node at index = 1.

Heap.build(options)

• options Object see new Heap(options) documentation

Creates a new Heap and if given options.heap will ensure that the returned heap satisfies the heap property dictated by options.kind.

Heap.left(index)

• index Integer index of a node to find the left child of

Returns the index of the left child for the node at index index.

WARNING: this method is not safe, invalid input is not checked

Heap.parent(index)

• index Integer index of a node to find the parent of

Returns the index of the parent for the node at index index.

WARNING: this method is not safe, invalid input is not checked

Heap.right(index)

• index Integer index of a node to find the right child of

Returns the index of the right child of the node at index index.

WARNING: this method is not safe, invalid input is not checked

new Heap(options)

• options:
  • heap: Array An optional array that will be used as initial heap state and not modified to satisfy the heap property.
  • kind: String One of min-heap, max-heap (default: max-heap)

Creates a new Heap.

heap.dump()

Dumps the present contents of storage used for the heap. The dump may include elements beyond heap size.

heap.maxHeapify(index)

• index Integer index of the node where to begin the procedure

Ensures that the max-heap property is satisfied for the sub-tree rooted at index.

heap.size()

Returns heap size.